题目描述

成都是一座来了就不想走的城市。还因为成都是一座旅游城市。旅游景点有：古堰流碧、祠堂柏森、青城叠翠、草堂喜雨、西岭晴雪、江楼修竹、文殊朝钟、天台夕晖、青羊花会、宝光普照、......。

旅游公司为喜欢旅游的李老师提供了 n 个景点，每个景点有一个旅游价值 w ( |w|<=1000 )。

旅游价值越大的景点，花费也越大。因旅游经费的问题，李老师决定：选择不超过第 k ( 1 <= k <= n ) 大旅游价值的景点，并且最多 m ( 1 <= m <= n-k+1 ) 个景点旅游，使得旅游价值和最大。

李老师想知道 p ( p <= n ) 组 k 和 m ，每组旅游价值和最大是多少？

输入格式

第 1 行，一个整数 n ，表示景点的个数

第 2 行，由空格隔开 n 个整数,表示 n 个景点的旅游价值。

第 3 行，整数 p ，如题所述

第 4~3+p 行，每行由空格隔开的两整数 k 和 m ,如题所述。

数据范围

1 <= n , p <= $10^5$

输出格式

p 行，每行一个最大旅游价值和。

样例

5
5 -1 4 6 1
4
1 4
2 1
4 2
5 1

16
5
1
0

提示：可能存在多个旅游城市有相同的旅游价值。例如 5 个景点，其旅游价值排序后是 10 6 6 6 1 1，那么旅游价值第 4 大的是 6 ，而不旅游价值不超过 6 的景点有 6 6 6 1，并非是 6 1 。