Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito es ahora profesor en la Universidad de la Habana y quiere hacer un torneo entre los estudiantes. Fito tiene N estudiantes, y conoce el nivel de conocimiento $f_i$ del iésimo de ellos.

El formato de la competencia es de la siguiente manera. Primero Fito ordena a los estudiantes en orden no creciente de $f_i$, luego el primer estudiante compite contra todos los demás juntos. Fito sabe de antemano que la competencia solo depende del conocimiento por lo que el estudiante gana si su conocimento no es menor que el total de fuerza de todos sus oponentes. En dicho caso el es considerado uno de los ganadores , de lo contrario pierde. En cualquier caso luego del match Fito se retira de la fila y el torneo continua. Nuevamente el de mayor conocimiento compite contra todos los demás en el mismo formato, si gana es considerado uno de los ganadores y luego sale de la fila y el torneo continua. Asi hasta que queda un solo estudiante, que se convierte automáticamente en ganador.

Fito quiere saber el total de ganadores. Sin embargo, como el torneo es pospuesto una y otra vez, el conocimiento de los estudiantes cambia con el tiempo. Ayuda a Fito a computar el total de ganadores después de cada cambio.

Input

La primera línea contiene un entero $N$, el número de estudantes$(1 \le N \le 100 000)$.

La segunda línea contiene $N$ enteros $f_1, f_2, ..., f_N$, la cantidad de conocimiento de cada estudiante $(1 \le fi \le 10^{12})$.

La tercera línea contene un entero $M(0 \le M \le 50 000)$, el número de cambios de fuerza en estudiantes.

Las siguientes M líneas contenen información acerca de los cambios. La iésima línea describe el iésmo cambio y contiene dos enteros $k$ y $v$, la cantidad de conocimiento en el k -ésimo estudiante se convierte en $v(1 \le k \le N, 1 \le v \le 10^{12})$

Output

Imprima $M + 1$ líneas cada una conteniendo un único entero.

En la primera línea imprima la cantidad de ganadores antes de que se haga ningún cambio. En la línea $i+1$ para cada $i>0$, imprima la cantidad de ganadores si la competencia fuera echa luego del iésmo cambio.

Sample test(s)