Symmetric Histogram Slicing

Consider an odd‐numbered histogram with (N) bars, where the height of the (i)-th bar is (v_i) for (1 \le i \le N). It is guaranteed that (N) is odd and that the bar at position (c = \frac{N+1}{2}) is one of the global maximums. Let (\mathrm{mx} = v_c).

For any ordered pair of integers ((A,B)) satisfying (0 \le A < B \le \mathrm{mx}), define the extracted portion of the histogram as those bars whose heights lie in the interval ([A,B]) (inclusive). We say that the pair ((A,B)) is good if the extracted portion is symmetric with respect to the vertical line passing through the center bar (position (c)). In other words, for every index (i) (with its symmetric counterpart (j = N+1-i)), either both (v_i) and (v_j) lie in ([A,B]) or neither does. (The center bar is always symmetric with itself.)

There are (Q) point updates on the array (v). For each state (i) (with (i=0) corresponding to the initial histogram and (1 \le i \le Q) corresponding to state after the (i)-th update), output the number of good pairs ((A,B)) (with (0 \le A < B \le \mathrm{mx})) for the current histogram. It is guaranteed that no update violates the property that (v_c) is one of the global maximums.

Input constraints and further details:

• The first line contains two integers (N) and (Q).
• The second line contains (N) integers (v_1, v_2, \dots, v_N), where (v_c) (with (c = \frac{N+1}{2})) is one of the global maximums.
• Each of the following (Q) lines contains two integers (pos) and (new) representing a modification: update (v_{pos}) to the value (new).\
• After each update (and in the initial state), you must count the number of good pairs ((A,B)) with (0 \le A < B \le \mathrm{mx}) for the current histogram.

Note: The problem guarantees that the histogram heights and updates are such that (v_c) remains a global maximum after every update.

Hint: A brute force solution that iterates over all (A, B) pairs and checks symmetry for every symmetric pair ((i, N+1-i)) is acceptable if the inputs are small. Otherwise, some precomputation or smarter enumeration may be necessary.

inputFormat

The input begins with a line containing two space‐separated integers (N) and (Q). The second line contains (N) space‐separated integers representing the histogram heights (v_1, v_2, \dots, v_N). Each of the next (Q) lines contains two space‐separated integers (pos) and (new), indicating that the value at position (pos) is updated to (new). (It is 1-indexed.)

outputFormat

Output (Q+1) lines. The first line corresponds to the initial state (before any updates) and each of the following (Q) lines corresponds to the answer after each update. Each line should contain a single integer: the number of good pairs ((A,B)) for the current histogram.

sample

3 1
3 7 4
3 7

19
7