There are NN (1≤N≤20001≤N≤2000) evenly spaced mountains in a row on the edge of Farmer John's farm. These can be expressed as an array of heights h1,h2,…,hNh1,h2,…,hN. For a mountain ii, you can see another mountain jj if there are no mountains strictly higher than the line of sight connecting the tops of mountain jj and ii. Formally, for two mountains i<ji<j, they can see each other if there is no kk such that i<k<ji<k<j and (k,hk)(k,hk) is above the line segment connecting (i,hi)(i,hi) and (j,hj)(j,hj). There are QQ (1≤Q≤20001≤Q≤2000) updates where the height of one mountain increases. Find the total number of unordered pairs of mountains that see each other after each update.
INPUT FORMAT (input arrives from the terminal / stdin):
Line 11 contains NN.Line 22 contains NN heights h1,h2,…,hNh1,h2,…,hN (for each ii, 0≤hi≤1090≤hi≤109).
Line 33 contains QQ.
Lines 44 to 3+Q3+Q contain xx, yy (1≤x≤N1≤x≤N, 1≤y1≤y) where xx is the index of the mountain and yy is the amount the height increases by. It is guaranteed that the new height of the mountain is at most 109109.
OUTPUT FORMAT (print output to the terminal / stdout):
QQ lines, with the total number of unordered pairs of mountains that see each other after each update.
SAMPLE INPUT:
5
2 4 3 1 5
3
4 3
1 3
3 2
SAMPLE OUTPUT:
7
10
7
Initially, the following pairs of mountains can see each other: (1,2)(1,2), (2,3)(2,3), (2,5)(2,5), (3,4)(3,4), (3,5)(3,5), (4,5)(4,5), a total of 66.
After the first update, mountain 44 has a height of 44, which doesn't block any visibility but does make it so that 44 can now see 22, making the new answer 77.
After the second update, mountain 11 has a height of 55, which doesn't block any visibility but does make it so that 11 can now see 33, 44, and 55, making the new answer 1010.
After the third update, mountain 33 has a height of 55, which blocks mountain 11 from seeing mountain 44, blocks mountain 22 from seeing mountains 44 and 55, and doesn't allow itself to see any more mountains since it can already see all of them, making the new answer 77.
SCORING:
Tests 2-5 satisfy N,Q≤100N,Q≤100.
Tests 6-11 satisfy Q≤10Q≤10.
Tests 12-21 have no additional constraints.
Problem credits: Joe Li and Larry Xing