Айданада \(n\) қораптан тұратын бір қатар бар. \(i\)-ші қорапта \(a_i\) кубик бар.

Бірнеше қатар тұрған қораптарда дәл \(1, 2, 3, \ldots\) кубиктер орналасқан болса, Айдана оларды сатылар деп атайды. Ол кез келген қораптан кубиктердің бір бөлігін лақтырып тастай алады (яғни санын азайта алады), бірақ кубиктерді қосуға болмайды.

Айданаға \(l\)-ші мен \(r\)-ші қораптар арасындағы сегмент берілген. Ол осы сегменттің ішінде қатар тұрған бірнеше қорапты таңдап, одан артық кубиктерді лақтырып тастап, \(1, 2, 3, \ldots, k\) сатысын алғысы келеді. Ол максималды \(k\) мәнін қанша алуға болатынын білгісі келеді.

Енгізу

Бірінші жолда бір бүтін сан \(n\) \((1 \leq n \leq 10^6)\) — қораптар саны берілген.

Екінші жолда \(n\) бүтін сан \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^6)\) — әр қораптағы кубиктер саны берілген.

Үшінші жолда бір бүтін сан \(q\) \((1 \leq q \leq 10^6)\) — сұраулар саны берілген.

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

Шығару

Әр сұрау үшін бір бүтін сан шығарыңыз — Айдана ала алатын максималды \(k\) мәні.

Мысалдар

Енгізу 1

8
10 1 2 3 8 5 6 7
2
1 8
4 7

Жауап 1

7
4