%
% Summer Russian training informatics camp for school students
% Thursday, June 30, 2016
%
% Problem: Egor Shcherbin
% Tests:
% Solutions: Mikhail Ipatov, Egor Shcherbin
% Idea: Egor Shcherbin
%
\begin{problem}{Histogram}{\textsl{standard input}}{\textsl{standard output}}{2 seconds}{512 megabytes}

Histogram with dimensions of $n \times m$ is a set of $n$ consecutive rectangles 
called columns; the $i$-th column has a size of $1 \times h_i$, the columns are placed 
inside a rectangle of size $n \times m$, which is called the border. 
Every column is adjacent to the bottom of the border with its side of length $1$.

For example, that's how the histogram of size $5 \times 4$ with heights $2$, $1$, $3$, $4$ and $1$ looks:

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

You are given a histogram of size $n \times m$. The left side of the border is a
light source. Let's call a point inside the border lit if the perpendicular, 
dropped on the left side of the border, doesn't cross the inside of any columns. 
Write a programm that, given the lengths of the columns, calculates the area of the 
lit part. The light doesn't cross the histogram's border.

For example, for the histogram at the picture above the answer is~$5$.

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

In addition to that, there are $q$ requests, the $i$-th request specifies
that the column with number $p_i$ changes its length to $a_i$. You have 
to recalculate the area of the lit part after every request.

\InputFile

The first line has three integers $t$, $n$, and $m$ "--- the number of 
the subgroup and the size of the histogram.

The second line has $n$ integers $h_1,\ldots,h_n$ ($0 \le h_i \le m$) "--- the
initial heights of the columns.

The third line contains an integer $q$ "--- the number of requests.
The $i$-th of the following $q$ lines has two integers $p_i$ and $a_i$
($1 \le p_i \le n$, $0 \le a_i \le m$).

\OutputFile

Print $q+1$ integers $s_0,s_1,\ldots,s_q$, where $s_0$ is the initial 
area of the lit part, $s_i$ "--- the area of the lit part after the $i$-th 
change.

\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}
\exmpfile{001.t}{001.a.t}%
\exmpfile{002.t}{002.a.t}%
\end{example}

\end{problem}
