Counting Six-Ring Structures

You are given a sequence \(a_0, a_1, \dots, a_n, a_{n+1}\) where \(a_0=a_{n+1}=+\infty\) and the values \(a_1, a_2, \dots, a_n\) are provided as input. For every index \(x\) with \(1\le x\le n\), define two neighbors as follows:

• The left neighbor of \(x\) is \(L(x)=\max\{0\le i<x \mid a_i\ge a_x\}\).
• The right neighbor of \(x\) is \(R(x)=\min\{xa_x\}\).

We also require that the neighbor relation is symmetric; that is, if \(x\) is adjacent to \(y\) then \(y\) is adjacent to \(x\).

A set of six distinct indices \(\{b_1,b_2,b_3,b_4,b_5,b_6\}\) (with \(0\le b_i\le n+1\)) forms a six‐ring if there exists an ordering of these indices such that for every \(i=1,2,\dots,6\) (with the convention that \(b_7=b_1\)), the indices \(b_i\) and \(b_{i+1}\) are neighbors. (Two six‐rings are considered the same if they contain the same set of indices, regardless of the order.)

There are \(m\) modification operations. In each operation you are given two integers \(x\) and \(y\) (with \(1\le x\le n\) and \(y\ge 1\)); you should update \(a_x\) by adding \(y\) (i.e. \(a_x := a_x+y\)). After each modification, recompute the neighbor relationships and output the number of six‐rings in the current graph.

All numbers are integers and the constraints are:

• \(1\le n, m\le 5\times 10^5\)
• \(1\le a_i, y\le 10^9\)

Note: For the purposes of this problem, you may assume that the input sizes in the test cases are small enough to allow a brute-force re‐computation after each update.

inputFormat

The first line contains two integers \(n\) and \(m\) indicating the number of sequence elements and the number of modifications, respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) separated by spaces.

Each of the next \(m\) lines contains two integers \(x\) and \(y\), representing a modification: increase \(a_x\) by \(y\).

outputFormat

For each modification operation, output on a separate line the number of six‐rings in the current neighbor graph.

sample

3 2
1 2 3
1 1
2 2

0
0