Six Cycle Counting

You are given a sequence \(a_0, a_1, a_2, \dots, a_n, a_{n+1}\) such that \(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:

• Let \(L(x)=\max\{i\mid 0\le i<x,\; a_i\ge a_x\}\). Then we say that \(L(x)\) and \(x\) are adjacent.
• Let \(R(x)=\min\{i\mid xa_x\}\). Then we say that \(R(x)\) and \(x\) are adjacent.

The adjacent relation is symmetric: if \(x\) and \(y\) are adjacent then so are \(y\) and \(x\).

A set \(\{b_1,b_2,b_3,b_4,b_5,b_6\}\) of six distinct indices (each between \(0\) and \(n+1\)) is called a six cycle if there exists an ordering \(b_1, b_2, b_3, b_4, b_5, b_6\) such that for every \(i=1,2,3,4,5\), \(b_i\) is adjacent to \(b_{i+1}\) and also \(b_6\) is adjacent to \(b_1\). (Two six cycles are considered the same if they contain the same set of vertices.)

There are \(m\) modification operations. In each operation, you are given two integers \(x\) and \(y\) and you must update \(a_x\) to \(a_x+y\). After each modification, recalculate the adjacent relationships according to the definitions above and output the number of six cycles present.

Note: In all formulas, use LaTeX formatting for mathematical expressions.

inputFormat

The first line contains two integers \(n\) and \(m\) where \(n\) is the number of elements in the sequence (excluding \(a_0\) and \(a_{n+1}\)) and \(m\) is the number of modification operations.

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

Then \(m\) lines follow, each containing two integers \(x\) and \(y\) representing an operation that increases \(a_x\) by \(y\) (\(1\le x\le n\)).

outputFormat

For each modification operation, output a single line containing the number of six cycles after the operation.

sample

1 1
1
1 1

0