水羊羹是一種以紅豆沙製成的日式甜點。它的製作方式是將紅豆沙與寒天一起煮，再凝固成長方形。

現在，JOI-kun 有一台水羊羹機。使用這台機器，JOI-kun 可以製作橫向較長、帶有 $N-1$ 條垂直切線的長方形水羊羹。水羊羹的長度與切線位置由機器上設定的 $N$ 個參數 $d_1,d_2,\ldots,d_N$ 決定。水羊羹的長度為 $d_1+d_2+\cdots+d_N$。從左邊數第 $i-1$ 條切線（$1\le i\le N$）到第 $i$ 條切線之間的距離為 $d_i$。這裡，將水羊羹最左端的邊視為第 $0$ 條切線，最右端的邊視為第 $N$ 條切線。最初，水羊羹機的參數滿足 $d_i=L_i$（$1\le i\le N$）。

JOI-kun 計畫舉辦 $Q$ 場茶會。第 $j$ 場茶會（$1\le j\le Q$）由整數 $X_j,Y_j,A_j,B_j$ 描述，依照以下流程進行。

1. 更新水羊羹機的參數 $d_{X_j}$，將它設為 $Y_j$。
2. JOI-kun 使用水羊羹機製作一份新的水羊羹。他取出第 $A_j$ 條切線到第 $B_j$ 條切線之間的部分，用於茶會，其餘部分由他吃掉。
3. JOI-kun 沿著其中一些切線切開供茶會使用的水羊羹部分，將它切成一塊或多塊。這個過程必須滿足以下條件：若依照原本的位置將各塊由左至右排列，各塊長度所形成的序列必須是鋸齒狀序列。

這裡，若序列中的元素交替增加和減少，便稱為鋸齒狀序列。例如，序列 $(2,9,2,7)$、$(7,1,9,4,6)$、$(5)$、$(2,1)$ 是鋸齒狀序列，而 $(1,2,3)$、$(7,1,4,4,6)$、$(2,2)$ 則不是。精確地說，若序列 $(x_1,x_2,\ldots,x_m)$ 滿足下列條件之一（或兩者都滿足），便稱為鋸齒狀序列：

• 對於 $k=1,2,\ldots,m-1$，若 $k$ 為奇數，則滿足不等式 $x_k<x_{k+1}$；若 $k$ 為偶數，則滿足不等式 $x_k>x_{k+1}$。
• 對於 $k=1,2,\ldots,m-1$，若 $k$ 為奇數，則滿足不等式 $x_k>x_{k+1}$；若 $k$ 為偶數，則滿足不等式 $x_k<x_{k+1}$。

由於 JOI-kun 希望把水羊羹分給盡可能多的朋友，他希望讓茶會流程 3 所得到的塊數盡可能多。

請撰寫程式，給定水羊羹機的初始參數與茶會計畫，對每場茶會計算將供茶會使用的水羊羹部分切開、且滿足條件時，最多能得到多少塊。請注意，在本題的限制下，一定可以將這部分水羊羹切成滿足條件的形式。

輸入格式

從標準輸入讀入以下資料。

$$ \begin{gathered} N\\ L_1\ L_2\ \cdots\ L_N\\ Q\\ X_1\ Y_1\ A_1\ B_1\\ X_2\ Y_2\ A_2\ B_2\\ \vdots\\ X_Q\ Y_Q\ A_Q\ B_Q \end{gathered} $$

輸出格式

向標準輸出輸出 $Q$ 行。第 $j$ 行（$1\le j\le Q$）對應第 $j$ 場茶會，應包含將該場茶會使用的水羊羹部分切開、且滿足條件時，最多能得到的塊數。

資料範圍

• $1\le N\le 250\,000$。
• $1\le L_i\le 10^9$（$1\le i\le N$）。
• $1\le Q\le 50\,000$。
• $1\le X_j\le N$（$1\le j\le Q$）。
• $1\le Y_j\le 10^9$（$1\le j\le Q$）。
• $0\le A_j<B_j\le N$（$1\le j\le Q$）。
• 所有給定的值都是整數。

子任務

1. （6 分）$N\le 200$，$Q\le 10$。
2. （9 分）$N\le 2\,000$，$Q\le 10$。
3. （13 分）$Q\le 10$。
4. （32 分）$Y_j=L_{X_j}$（$1\le j\le Q$）。
5. （29 分）$L_i\le 120\,000$（$1\le i\le N$），$Y_j\le 120\,000$（$1\le j\le Q$）。
6. （11 分）無額外限制。

範例

輸入格式 1

6
5 6 8 7 4 9
1
6 9 0 5

輸出格式 1

3

說明

在第一場茶會中，水羊羹機的參數被設為 $(d_1,d_2,d_3,d_4,d_5,d_6)=(5,6,8,7,4,9)$。JOI-kun 使用第 $0$ 條切線到第 $5$ 條切線之間的水羊羹部分，如圖 1 所示。

圖 1. 供茶會使用的水羊羹

例如，JOI-kun 可以如下切開這部分水羊羹。

圖 2. 切開水羊羹的三種方法。由上至下依序為方法 1、方法 2、方法 3。

在方法 1 中，各塊的長度為 $5,14,7,4$。由於這個序列不是鋸齒狀序列，因此不滿足條件。另一方面，在方法 2 中，各塊的長度為 $11,8,11$。由於這個序列是鋸齒狀序列，因此滿足條件。在方法 3 中，這一塊的長度為 $30$。由於這個序列是鋸齒狀序列，因此也滿足條件。

若 JOI-kun 使用方法 2 切開這部分水羊羹，他會得到 3 塊。由於不可能將這部分水羊羹切成滿足條件且得到 4 塊或更多塊，因此在第一行輸出 3。

此範例輸入滿足所有子任務的限制。

輸入格式 2

4
6 2 3 6
3
3 2 1 3
4 5 1 4
1 1 0 4

輸出格式 2

1
2
3

說明

在第一場茶會中，供茶會使用的水羊羹部分長度為 $4$。有一條切線距離最左端的邊為 $2$。若 JOI-kun 不切開水羊羹便直接使用，他會得到一塊。各塊長度的序列為 $(4)$，是鋸齒狀序列。由於他無法得到多於一塊，因此輸出 1。

在第二場茶會中，供茶會使用的水羊羹部分長度為 $9$。有兩條切線距離最左端的邊分別為 $2,4$。若 JOI-kun 在距離最左端的邊為 $4$ 的切線切開水羊羹，他會得到兩塊。各塊長度的序列為 $(4,5)$，是鋸齒狀序列。由於他無法得到多於兩塊，因此輸出 2。

在第三場茶會中，供茶會使用的水羊羹部分長度為 $10$。有三條切線距離最左端的邊分別為 $1,3,5$。若 JOI-kun 在距離最左端的邊為 $3,5$ 的切線切開水羊羹，他會得到三塊。各塊長度的序列為 $(3,2,5)$，是鋸齒狀序列。由於他無法得到多於三塊，因此輸出 3。

此範例輸入滿足子任務 1、2、3、5、6 的限制。