#T. 搭建壁垒

Type: RemoteJudge

1000ms

256MiB

题目描述

战场上，♙正在为队友搭建一堵墙壁以抵挡敌方火力。目前，他有种类 $i$ 的砖头共 $a_i$ 个。如果要搭建一堵高 $h$ 的墙，他需要种类 $0\sim h-1$ 的砖头各一个。为了保证战友的安全，他希望搭建若干堵墙使得总高度之和尽可能大。

但是战场上瞬息万变，有些时候敌方会炸毁一块某一种类型的砖头，有些时候友方会运来一块某一种类型的砖头，你需要在战斗开始前以及每一次战局发生变化后输出能搭建的墙的总高度之和最大值。

第一行一个正整数 $n$ ，表示砖头的种类数。

第二行 $n$ 个正整数 $a_0,a_1,\cdots a_{n-1}$ 。

第三行，一个正整数 $q$ 表示战局变化的次数。

接下来 $q$ 行，每行两个正整数 $o,x$ 。

$q+1$ 行，表示答案。

$1\le n,q\le 2\times10^5$ ， $1\le a_i\le 10^6$ 。