Problem Statement

For an integer sequence $x=(x_1,x_2,\cdots,x_N)$ of length $N$ with each element being between $0$ and $M$, inclusive, we define $f(x)$ as follows:

• Prepare an integer sequence $y=(y_1,y_2,\cdots,y_M)$ of length $M$. Initially, set all elements of $y$ to $0$. Then, for each $i=1,2,\cdots,N$, in order, perform the following operations:
• For each integer $j$ ($1 \leq j \leq x_i$), replace the value of $y_j$ with $\max(y_j-1,0)$.
  • For each integer $j$ ($x_i < j \leq M$), replace the value of $y_j$ with $y_j+1$.
• The sum of the elements of $y$ after all operations is the value of $f(x)$.

You are given an integer sequence $A=(A_1,A_2,\cdots,A_N)$ of length $N$ with each element being between $0$ and $M$, inclusive. Process $Q$ queries:

• The $i$-th query: Given integers $X_i$ and $Y_i$, replace the value of $A_{X_i}$ with $Y_i$. Then, print the value of $f(A)$.

Constraints

• $1 \leq N,M,Q \leq 250000$
• $0 \leq A_i \leq M$
• $1 \leq X_i \leq N$
• $0 \leq Y_i \leq M$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M Q
A_1 A_2 \cdots A_N
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q

Output

Print the answer.