水羊羹係一種用紅豆蓉整嘅日本甜點，做法係將紅豆蓉同寒天煮埋，再喺長方形模具入面凝固。

而家，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 得到嘅塊數盡可能多。

畀定水羊羹機嘅初始參數同茶會計劃，請寫一個程式，對每次茶會計算將嗰部分水羊羹切開後，喺滿足條件下最多可以得到幾多塊。留意，喺呢題嘅限制下，一定可以將嗰部分水羊羹切成滿足條件嘅形狀。

輸入格式

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

N
L_1 L_2 ... L_N
Q
X_1 Y_1 A_1 B_1
X_2 Y_2 A_2 B_2
...
X_Q Y_Q A_Q B_Q

輸出格式

向標準輸出寫出 $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$ 嘅限制。