that are on the segment from the
lith to the
rith element".
A subsequence of the sequence a1 , ..., an is a sequence that can be obtained by removing several ai elements (the relative order of the remaining
elements cannot be changed). So, for example, the sequence (2, 4) is a subsequence of the sequence (1, 2, 3, 4, 5) (you can delete the elements 1, 3 and 5 ), and the sequence (5, 1) is not.< br />
Input
The first line contains an integer
n (1 <= n <= 3000 ) is the number of elements in the sequence. The second line contains
n Numbers separated by spaces are the elements of the sequence. All elements do not exceed 10
9 in absolute value. The third line contains a single integer
q (1 < ;= q <= 10
5) - number of requests. The following
q lines describe the queries. Description of the
i -th query - two numbers
li and
rj (1 <= l
i <= r
i <= n) , separated by spaces.
Output data
Output q numbers - answers to queries. Numbers should be output one per line in the same order as the queries are described in the input.
Examples
| # |
Input |
Output |
| 1 |
6
3 3 -5 7 4 9
6
14
1 2
23
15
3 5
25 |
2
1
1
2
2
2 |