Програмчлалын олимпиадын бодлогын архив

Батад a₁, a₂, . . . , a_n жагсаалт болон q хүсэлт өгөгдсөн. Хүсэлтүүд нь дараах хэлбэртэй байна.

Хүсэлт нь l болон r гэсэн хос тооноос бүтнэ. Таны даалгавар бол l-с r завсар дахь элементүүд болон индексийн нийлбэрийг олох юм. Өөрөөр хэлбэл:

Input

Эхний мөрөнд n(1 ≤ n ≤ 10⁵)  тоо өгөгдөнө. Хоёр дахь мөрөнд хоосон зайгаар тусгаарлагдсан n элементтэй a₁, a₂, . . . , a_n(|a_i|≤ 10⁹) жагсаалт өгөгдөнө.
Дараагийн мөрөнд хүсэлт болох q тоо өгөгдөнө. Дараагийн q (1 ≤ q ≤ 10⁵) ширхэг мөр бүрт l_i,r_i (1 <=l_i, r_i <=n) хос тоо өгөгдөнө.

Output

Хүсэлт болгоны хувьд хариуг орж ирсэн дараалалын дагуу хэвлэнэ.

Example

Input:

10
1 2 3 4 5 6 7 8 9 10
2
5 6
3 8
Output:
22

66