Mizuyokan Tea Party and Zigzag Partition

Mizuyokan is a traditional Japanese confectionery made from azuki bean paste. JOI-kun now owns a mizuyokan machine which produces a horizontally long rectangular mizuyokan. The machine has N parameters \(d_1, d_2, \dots, d_N\) which determine the lengths of the consecutive segments of the produced mizuyokan. Specifically, the length of the mizuyokan is \(d_1+d_2+\cdots+d_N\). Imagine placing cutlines at the left edge (considered as the 0-th cutline), after each segment (cutlines 1 through \(N-1\)) and at the right edge (the \(N\)-th cutline).

Initially, the machine is set to \(d_i = L_i\) for \(1 \le i \le N\). JOI-kun then plans to hold \(Q\) tea parties. The \(j\)-th tea party is described by four integers \(X_j, Y_j, A_j, B_j\) and proceeds as follows:

1. The machine parameter \(d_{X_j}\) is updated to \(Y_j\).
2. The machine is used to produce a mizuyokan, and JOI-kun takes the part between the \(A_j\)-th and \(B_j\)-th cutlines (i.e. the segments \(d_{A_j+1}, d_{A_j+2}, \dots, d_{B_j}\)); the remainder is discarded.
3. He then makes further cuts along some of the existing cutlines within this piece to partition it into one or more contiguous pieces. The only constraint is that if the pieces (with lengths \(x_1,x_2,\dots,x_m\)) are considered in left-to-right order, then the sequence must be zigzag.

A sequence \((x_1,x_2,\dots,x_m)\) is said to be zigzag if either of the following conditions holds:

• For every \(k=1,2,\dots,m-1\): \[ \begin{cases} x_k x_{k+1} &\text{if } k \text{ is even}. \end{cases} \]
• For every \(k=1,2,\dots,m-1\): \[ \begin{cases} x_k > x_{k+1} &\text{if } k \text{ is odd},\\ x_k < x_{k+1} &\text{if } k \text{ is even}. \end{cases} \]

Since JOI-kun wishes to share as many pieces of mizuyokan as possible with his friends, for each tea party he wants to maximize the number of pieces while satisfying the zigzag condition. Your task is, given N, Q, the initial parameters \(L_1, L_2,\dots,L_N\) and the description of each tea party, to compute for each tea party the maximum possible number of pieces that can be obtained.

Note: Under the constraints of this problem, it is always possible to partition the selected part of the mizuyokan into pieces satisfying the zigzag condition.

inputFormat

The first line contains two integers \(N\) and \(Q\) separated by a space.

The second line contains \(N\) integers \(L_1, L_2, \dots, L_N\) separated by spaces, representing the initial parameters of the mizuyokan machine.

Then \(Q\) lines follow. The \(j\)-th line contains four integers \(X_j, Y_j, A_j, B_j\) separated by spaces, describing the update and tea party details. Here, \(X_j\) (\(1 \le X_j \le N\)) denotes which parameter to update, \(Y_j\) is the new value for that parameter, and \(0 \le A_j < B_j \le N\) where the segment of the mizuyokan used for the tea party is between the \(A_j\)-th and \(B_j\)-th cutlines. Note that the \(i\)-th segment of the produced mizuyokan corresponds to the current \(d_i\) (with 1-indexed \(i\)).

outputFormat

For each tea party, output a single line containing the maximum possible number of pieces the chosen part can be partitioned into, preserving a zigzag sequence of piece lengths.

sample

5 3
2 9 2 7 1
2 3 0 3
5 10 1 5
1 1 0 5

3
3
4