물양갱(미즈요칸)은 팥 앙금으로 만드는 일본의 과자이다. 팥 앙금을 한천과 함께 끓인 뒤 직사각형 모양의 틀에 굳혀서 만든다.

지금 JOI 군은 물양갱 기계를 가지고 있다. 이를 사용하면 JOI 군은 $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 군은 $Q$번의 다과회를 열 계획이다. $j$번째 다과회($1\le j\le Q$)는 정수 $X_j,Y_j,A_j,B_j$로 설명되며, 다음과 같이 진행된다.

1. 물양갱 기계의 매개변수 $d_{X_j}$가 갱신되어 $Y_j$로 설정된다.
2. JOI 군은 물양갱 기계를 사용하여 새로운 물양갱을 만든다. 그는 물양갱에서 $A_j$번째 절취선과 $B_j$번째 절취선 사이의 부분을 가져와 다과회에 사용하고, 나머지는 자신이 먹는다.
3. JOI 군은 다과회용 물양갱 조각을 몇 개의 절취선을 따라 자른다. 그는 그 물양갱 부분을 한 개 이상의 조각으로 나눈다. 이 과정에서 다음 조건이 만족되어야 한다: 조각들을 원래 위치처럼 왼쪽부터 순서대로 나열했을 때, 조각들의 길이 수열이 지그재그(zigzag)여야 한다.

여기서 수열의 원소들이 번갈아 가며 증가하고 감소할 때 그 수열을 지그재그라고 부른다. 예를 들어 수열 $(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 군은 가능한 한 많은 친구들에게 물양갱을 나누어 주고 싶기 때문에, 다과회의 과정 3.을 통해 얻어지는 조각의 개수를 최대화하고 싶다.

물양갱 기계의 초기 매개변수에 대한 정보와 다과회 계획이 주어졌을 때, 각 다과회에 대해 조건을 만족하도록 물양갱의 일부를 잘라 얻을 수 있는 조각의 최대 개수를 계산하는 프로그램을 작성하시오. 이 문제의 제한 아래에서는 조건을 만족하도록 물양갱의 일부를 자르는 것이 항상 가능함에 유의하라.

입력

표준 입력으로부터 다음 데이터를 읽어들인다.

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

출력

표준 출력에 $Q$개의 줄을 출력한다. 출력의 $j$번째 줄($1\le j\le Q$)은 $j$번째 다과회에 대응한다. 이 줄에는 $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 군은 그림 1과 같이 $0$번째 절취선과 $5$번째 절취선 사이의 물양갱 부분을 사용한다.

그림 1. 다과회에 사용할 물양갱

예를 들어, JOI 군은 물양갱의 해당 부분을 다음과 같이 자를 수 있다.

그림 2. 물양갱을 자르는 세 가지 방법. 위에서부터 방법 1, 방법 2, 방법 3.

방법 1에서 조각들의 길이는 $5,14,7,4$이다. 이 수열은 지그재그가 아니므로 조건을 만족하지 않는다. 반면 방법 2에서 조각들의 길이는 $11,8,11$이다. 이 수열은 지그재그이므로 조건을 만족한다. 방법 3에서 조각의 길이는 $30$이다. 이 수열도 지그재그이므로 조건을 만족한다.

JOI 군이 물양갱의 해당 부분을 방법 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 군이 물양갱을 자르지 않고 그대로 사용하면 한 개의 조각을 얻는다. 조각들의 길이 수열은 $(4)$이며 이는 지그재그이다. 한 개보다 많은 조각을 얻을 수 없으므로 1을 출력한다.

두 번째 다과회에서 다과회용 물양갱 부분의 길이는 $9$이다. 가장 왼쪽 끝에서 거리가 $2,4$인 두 개의 절취선이 있다. JOI 군이 가장 왼쪽 끝에서 거리가 $4$인 절취선에서 물양갱을 자르면 두 개의 조각을 얻는다. 조각들의 길이 수열은 $(4,5)$이며 이는 지그재그이다. 두 개보다 많은 조각을 얻을 수 없으므로 2를 출력한다.

세 번째 다과회에서 다과회용 물양갱 부분의 길이는 $10$이다. 가장 왼쪽 끝에서 거리가 $1,3,5$인 세 개의 절취선이 있다. JOI 군이 가장 왼쪽 끝에서 거리가 $3,5$인 절취선들에서 물양갱을 자르면 세 개의 조각을 얻는다. 조각들의 길이 수열은 $(3,2,5)$이며 이는 지그재그이다. 세 개보다 많은 조각을 얻을 수 없으므로 3을 출력한다.

이 예제 입력은 서브태스크 $1,2,3,5,6$의 제한을 만족한다.