题目描述

豆豆从小对数字很敏感，小学里就显露出超常的能力，老师为了防止他太过骄傲，给了他一个可怕的难题：求一串给定整数某一段的平均值。每个整数都是小于2^31的。老师做梦也没想到豆豆全都回答出来了，原来豆豆有一个擅长编程的朋友你。

输入格式

第一行一个整数n(1≤n≤10^5)，表示一串整数的个数；

第二行用空格隔开的n个非负整数(0≤ai≤10^3)；

接下来m行，每行两个整数i和j(1≤i, j≤n)，表示询问第i个到第j个整数的平均值，不保证i<j。

输出格式

m行，每行一个数，表示平均值，结果取整数。

输入/输出样例

5
0 25 0 23 2
1
2 5

12

说明/提示

时间1000ms，内存256MiB