Mizuyokan — це японські солодощі з пасти з бобів адзукі. Їх готують, варячи пасту з бобів адзукі з агаром і даючи їй застигнути у прямокутній формі.

JOI-kun має машину для mizuyokan. За її допомогою він може виготовити горизонтально витягнутий прямокутний mizuyokan із $N-1$ вертикальними лініями розрізу. Довжина mizuyokan та положення ліній розрізу визначаються $N$ параметрами $d_1,d_2,\ldots,d_N$, установленими на машині. Довжина mizuyokan дорівнює $d_1+d_2+\cdots+d_N$. Відстань між $(i-1)$-ю та $i$-ю лініями розрізу зліва дорівнює $d_i$ $(1\le i\le N)$. Найлівіший край mizuyokan вважається $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 виготовляє новий mizuyokan за допомогою машини. Він бере частину між $A_j$-ю та $B_j$-ю лініями розрізу для чаювання, а решту з'їдає.
3. JOI-kun розрізає частину mizuyokan для чаювання вздовж деяких ліній розрізу на один або більше шматків. При цьому має виконуватися така умова: якщо впорядкувати шматки зліва направо відповідно до їхніх початкових положень, послідовність їхніх довжин має бути зигзагоподібною.

Послідовність називається зигзагоподібною, якщо її елементи почергово зростають і спадають. Наприклад, послідовності $(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 хоче пригостити mizuyokan якомога більше друзів, він хоче максимізувати кількість шматків, отриманих на кроці $3$ чаювання.

Напишіть програму, яка за початковими параметрами машини та планом чаювань для кожного чаювання обчислює найбільшу можливу кількість шматків, на які можна розрізати відповідну частину mizuyokan так, щоб виконувалася умова. За обмежень цієї задачі завжди можна розрізати частину mizuyokan так, щоб умова виконувалася.

Вхідні дані

Прочитайте зі стандартного вводу такі дані:

$$ \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$-му чаюванню та має містити найбільшу можливу кількість шматків, на які можна розрізати частину mizuyokan для цього чаювання так, щоб виконувалася умова.

Обмеження

• $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 2000$, $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 використовує частину mizuyokan між $0$-ю та $5$-ю лініями розрізу, як показано на рисунку $1$.

Рисунок 1. Mizuyokan для чаювання

Наприклад, JOI-kun може розрізати цю частину mizuyokan такими способами.

Рисунок 2. Три способи розрізати mizuyokan. Згори вниз: спосіб 1, спосіб 2, спосіб 3.

У способі $1$ довжини шматків дорівнюють $5,14,7,4$. Ця послідовність не є зигзагоподібною, тому умова не виконується. Натомість у способі $2$ довжини шматків дорівнюють $11,8,11$. Ця послідовність є зигзагоподібною, тому умова виконується. У способі $3$ довжина єдиного шматка дорівнює $30$. Ця послідовність також є зигзагоподібною, тому умова виконується.

Якщо JOI-kun розріже частину mizuyokan способом $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

Примітка

На першому чаюванні довжина частини mizuyokan для чаювання дорівнює $4$. Є лінія розрізу на відстані $2$ від її найлівішого краю. Якщо JOI-kun використає mizuyokan, не розрізаючи його, він отримає один шматок. Послідовність довжин шматків дорівнює $(4)$ і є зигзагоподібною. Оскільки отримати більше ніж один шматок неможливо, слід вивести $1$.

На другому чаюванні довжина частини mizuyokan для чаювання дорівнює $9$. Є дві лінії розрізу на відстанях $2,4$ від її найлівішого краю. Якщо JOI-kun розріже mizuyokan по лінії на відстані $4$ від найлівішого краю, він отримає два шматки. Послідовність довжин шматків дорівнює $(4,5)$ і є зигзагоподібною. Оскільки отримати більше ніж два шматки неможливо, слід вивести $2$.

На третьому чаюванні довжина частини mizuyokan для чаювання дорівнює $10$. Є три лінії розрізу на відстанях $1,3,5$ від її найлівішого краю. Якщо JOI-kun розріже mizuyokan по лініях на відстанях $3,5$ від найлівішого краю, він отримає три шматки. Послідовність довжин шматків дорівнює $(3,2,5)$ і є зигзагоподібною. Оскільки отримати більше ніж три шматки неможливо, слід вивести $3$.

Цей приклад задовольняє обмеження підзадач $1,2,3,5,6$.