Mizuyokan — японская сладость из пасты бобов адзуки. Её готовят, проваривая пасту с агаром и давая смеси застыть в прямоугольной форме.

У JOI-kun есть машина для приготовления mizuyokan. С её помощью он может приготовить вытянутую по горизонтали прямоугольную сладость с $N-1$ вертикальными линиями разреза. Длина сладости и положения линий разреза задаются $N$ параметрами машины $d_1,d_2,\ldots,d_N$. Длина сладости равна $d_1+d_2+\cdots+d_N$. Расстояние между $(i-1)$-й и $i$-й линиями разреза слева ($1 \le i \le N$) равно $d_i$. При этом левый край сладости считается нулевой линией разреза, а правый — $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$ выполняется $x_k<x_{k+1}$, если $k$ нечётно, и $x_k>x_{k+1}$, если $k$ чётно.
• Для $k=1,2,\ldots,m-1$ выполняется $x_k>x_{k+1}$, если $k$ нечётно, и $x_k<x_{k+1}$, если $k$ чётно.

JOI-kun хочет угостить как можно больше друзей, поэтому стремится максимизировать число кусочков, полученных на шаге 3 чаепития.

По заданным начальным параметрам машины и плану чаепитий напишите программу, которая для каждого чаепития вычисляет максимальное возможное число кусочков, на которые можно разрезать взятую часть сладости с соблюдением условия. Обратите внимание: при ограничениях этой задачи всегда можно разрезать эту часть так, чтобы условие выполнялось.

Входные данные

Считайте следующие данные из стандартного ввода.

$$ \begin{array}{l} 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{array} $$

Выходные данные

Выведите $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 использует часть сладости между нулевой и пятой линиями разреза, как показано на рисунке 1.

Рисунок 1. Сладость для чаепития.

Например, JOI-kun может разрезать эту часть следующим образом.

Рисунок 2. Три способа разрезать сладость. Сверху вниз: способ 1, способ 2, способ 3.

При способе 1 длины кусочков равны 5, 14, 7, 4. Эта последовательность не зигзагообразна, поэтому условие не выполняется. При способе 2 длины кусочков равны 11, 8, 11. Эта последовательность зигзагообразна, поэтому условие выполняется. При способе 3 получается один кусочек длины 30. Такая последовательность тоже зигзагообразна, поэтому условие также выполняется.

Разрезав сладость способом 2, JOI-kun получит 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.