题目描述

有一张由长度为 $n$ 的序列 $a_1, a_2, \cdots, a_n$ 表示的柱状图。柱状图上从左到右第 $i$ 根柱子的高度为 $a_i$，宽度为 $1$。

我们会对该柱状图进行 $q$ 次修改。第 $i$ 次修改可以记为一对整数 $(x_i, v_i)$，表示我们会将第 $x_i$ 根柱子的高度增加 $v_i$。

在每次修改之后，回答以下询问：如果下了一场大雨，雨水填满了柱状图上的每个坑洼，求这张柱状图中可以留存多少雨水。

更正式地，给定长度为 $n$ 的整数序列 $a_1, a_2, \cdots, a_n$，第 $i$ 次修改会将 $a_{x_i}$ 的值增加 $v_i$。在每次修改之后，回答以下询问：令 $f_i = \max(a_1, a_2, \cdots, a_i)$ 以及 $g_i = \max(a_i, a_{i + 1}, \cdots, a_n)$，计算

$$\sum\limits_{i = 1}^n \left( \min(f_i, g_i) - a_i \right) $$

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据：

第一行输入一个整数 $n$（$1 \le n \le 10^5$）表示柱状图中柱子的数量。

第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$1 \le a_i \le 10^6$），其中 $a_i$ 表示第 $i$ 根柱子的初始高度。

第三行输入一个整数 $q$（$1 \le q \le 10^5$）表示修改的次数。

对于接下来 $q$ 行，第 $i$ 行输入两个整数 $x_i$ 和 $v_i$（$1 \le x_i \le n$，$1 \le v_i \le 10^6$）表示第 $i$ 次修改将第 $x_i$ 根柱子的高度增加了 $v_i$。

保证所有数据 $n$ 之和与 $q$ 之和均不超过 $10^6$。

输出格式

每次修改输出一行一个整数表示柱状图中可以留存多少雨水。

2
6
1 2 3 4 5 6
2
1 2
3 3
5
100 10 1 10 100
1
3 100

1
4
180