%
% Летние всероссийские школьные учебно-тренировочные сборы по информатике
% Четверг, 30 июня 2016 года
%
% Условие: Егор Щербин
% Тесты:
% Решения: Михаил Ипатов, Егор Щербин
% Идея: Егор Щербин
%
\begin{problem}{Гистограмма}{\textsl{cтандартный ввод}}{\textsl{cтандартный вывод}}{2 секунды}{512 мегабайт}

Гистограммой размера $n \times m$ называется набор из $n$ подряд идущих
прямоугольников, называемых столбиками, $i$-й из которых имеет размер 
$1 \times h_i$, расположенных внутри
прямоугольника размера $n \times m$, называемого границей, и прилегающих своей 
единичной стороной к нижней стороне границы.

К примеру, так выглядит гистограмма $5 \times 4$ с высотами $2$, $1$, $3$, $4$ и
$1$:

\begin{center}
\includegraphics{pics/hist}
\end{center}

Дана гистограмма размера $n \times m$. Левая сторона границы служит источником
света; назовём точку внутри границы освещённой, если перпендикуляр, опущенный
на левую сторону границы не пересекается ни с одним из столбиков. 
Вам требуется написать программу, которая по длинам столбиков
определяет площадь освещённой области. Cчитается, что свет не выходит за границу
гистограммы.

Например, для приведённого выше примера площадь освещённой области равна~$5$.

\begin{center}
\includegraphics{pics/hist_lit}
\end{center}

В дополнение к этому, происходит $q$ запросов, при $i$-м столбик с номером $p_i$
изменяет свою длину на $a_i$. После каждого из этих изменений также неоходимо 
находить возможно изменившуюся площадь освещенной области.

\InputFile

Первая строка содержит два целых числа $t$, $n$ и $m$ "--- номер подгруппы и 
размеры гистограммы.

Вторая строка содержит $n$ целых чисел $h_1,\ldots,h_n$ ($0 \le h_i \le m$)
"--- изначальные длины столбиков.

Третья строка содержит целое число $q$ "--- количество запросов.
$i$-я из следующих $q$ строк содержат по два целых числа $p_i$ и $a_i$
($1 \le p_i \le n$, $0 \le a_i \le m$).

\OutputFile

Выведите $q+1$ целое число $s_0,s_1,\ldots,s_q$, где $s_0$ "--- изначальная
площадь освещённой области, $s_i$ "--- площадь освещённой области после $i$-го
изменения.

\Scoring

\SubtaskWithScore{10}
$1 \le q,n \le 10^4$, $0 \le m \le 10^9$

\SubtaskWithScore{20}
$q=n$, $n,m \le 10^5$, $1 \le n$, $0 \le m$, $1 \le n \cdot m \le 10^6$, $p_i = i$

\SubtaskWithScore{20}
$q=n$, $n,m \le 10^5$, $1 \le n$, $0 \le m$, $p_i = n+1-i$

\SubtaskWithScore{20}
$q=n$, $n,m \le 10^5$, $1 \le n$, $0 \le m$, $p_i = i$

\SubtaskWithScore{30}
$1 \le q,n \le 10^5$, $0 \le m \le 10^9$

\Examples

\begin{example}
\exmp{
0 1 1
1
1
1 0
}{
0 1 
}%
\exmp{
0 5 4
2 1 3 4 1
2
3 2
2 3
}{
5 6 4 
}%
\end{example}

\end{problem}
