04 Prosek

У једном граду прати се број купаца који улазе у тржни центар током дана.

Дат је низ од n интервала, где је за сваки интервал познат број купаца који су ушли у том периоду.

Након тога, задато је q упита. Сваки упит задаје један интервал [l, r], и потребно је одредити просечан број купаца (цео број) у том периоду. Потребно је да алгоритам буде ефикасан и да има временску сложеност O(n+q).

Улаз

У првој линији уноси се цео број: n (1 ≤ n ≤ 100000) — број интервала У другој линији уноси се низ: a₁, a₂, …, aₙ (0 ≤ aᵢ ≤ 1000) — број купаца у сваком интервалу У трећој линији: q (1 ≤ q ≤ 100000) — број упита У наредних q линија: по два броја l, r (1 ≤ l ≤ r ≤ n)

Излаз

За сваки упит исписати просечан број купаца (цео број) у одговарајућем интервалу [l, r].

Пример

Улаз

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

Излаз

3
3
3
2
4
4

Објашњење

[1,3]  (5+1+3)=9 → 9/3 = 3
[2,5]  (1+3+2+6)=12 → 12/4 = 3
[1,10]  збир свих  = 32 → 32/10 = 3
[4,4]  (2) → 2/1 = 2
[7,9]  (4+1+8)=13 → 13/3 = 4
[9,10]  (8+0)=8 → 8/2 = 4