Ұзындығы \(n\) болатын \(a\) жиымы берілген. Оның элементтері \(-1\), \(0\) және \(1\) сандарынан тұрады. Сізге \(q\) сұранысты өңдеу қажет.

Әрбір сұраныс \([l, r]\) кесіндісімен беріледі және осы \([l, r]\) кесіндінің ішінде толық орналасқан, элементтерінің қосындысы теріс емес болатын ең ұзын үздіксіз ішкі кесіндіні табу керек.

Ішкі кесінді — бұл жиымның \(a_x, a_{x+1}, \dots, a_y\) элементтерінің тізбегі, мұндағы \(l \leq x \leq y \leq r\). Ішкі кесіндінің қосындысы мынаған тең:

\(a_x + a_{x+1} + \dots + a_y\).

Мұндай барлық ішкі кесінділердің ішінде ең ұзын кесіндінің ұзындығын анықтау қажет, яғни \[a_x + a_{x+1} + \dots + a_y \geq 0\] шартын қанағаттандыратын ең үлкен \((y - x + 1)\) мәнін табу керек.

Егер берілген сұраныста қосындысы теріс емес ішкі кесінді болмаса, жауап \(0\) болады.

Енгізу

Бірінші жолда \(n\) \((1 \leq n \leq 3 \cdot 10^5)\) — жиымның ұзындығы беріледі.

Екінші жолда \(n\) бүтін сан \(a_1, a_2, \dots, a_n\) \((-1 \leq a_i \leq 1)\) беріледі.

Үшінші жолда \(q\) \((1 \leq q \leq 3 \cdot 10^5)\) — сұраныстар саны беріледі.

Келесі \(q\) жолдың әрқайсысында екі бүтін сан \(l\) және \(r\) \((1 \leq l \leq r \leq n)\) — сұраныс шекаралары беріледі.

Шығару

Әрбір сұраныс үшін бір бүтін санды шығару керек — \([l, r]\) кесіндісінің ішінде орналасқан және қосындысы теріс емес ең ұзын ішкі кесіндінің ұзындығы.

Мысалдар

Енгізу 1

7
1 -1 0 -1 1 -1 1
3
1 6
2 5
3 7

Жауап 1

5
3
5