Мидзуёкан — адзуки бұршағының пастасынан жасалатын жапон тәттісі. Ол адзуки бұршағының пастасын агармен бірге қайнатып, тіктөртбұрышты қалыпта қатыру арқылы дайындалады.

Қазір 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$-ішкі есептердің шектеулерін қанағаттандырады.