Visible Mountain Pairs

Farmer John's farm is lined with (N) mountains ((1 \le N \le 2000)) arranged in a row at equal intervals. The mountains have heights (h_1, h_2, \dots, h_N). Two mountains (i) and (j) (with (i < j)) can see each other if no mountain between them has its peak strictly above the line segment joining the peaks of mountains (i) and (j). In other words, for every mountain (k) with (i < k < j), the following must hold: [ h_k \le h_i + \frac{h_j - h_i}{j-i} \times (k-i) ]

You are also given (Q) update operations ((1 \le Q \le 2000)). Each update increases the height of one mountain. After each update, compute the total number of unordered pairs of mountains that can see each other. Note that two mountains (i) and (j) ((i < j)) form one pair, and each visible pair is counted exactly once.

inputFormat

The input begins with a line containing two integers (N) and (Q).\newline The next line contains (N) integers representing the initial heights: (h_1, h_2, \dots, h_N).\newline Then (Q) lines follow. Each of these lines contains two integers (p) and (d) indicating that the height of mountain (p) (1-indexed) increases by (d).

outputFormat

For each update operation, output a single line containing the number of unordered pairs of mountains that can see each other after performing that update.

sample

5 3
1 2 3 4 5
2 1
4 2
1 5

7
5
7