Topuch is the name of the brand new bubble tea shop just opened on your street. Just for a bubble tea lover like you :3

Touch and Top, the owners of the shop, think that the tea that comes after and have less sweetness than the previous one is unique. So they would consider the pair of tea that is unique as having the uniqueness value of 1. You've just finished reading the shop description and suddenly, a cute girl in pink come up to you and ask you if you can calculate the uniqueness of the range of the tea sequence for her. You have to help help her.... :3

The uniqueness in range L...R is defined by the number of the pair of (i,j) L<=i <= j<=R that the sweetness of tea at i is higher than the one at j.

Input

The first line contains a single number N denoting the size of the tea sequence. (1 <= N <= 5000)

The second line contains N numbers; Ai denoting the sweetness of each tea. (1 <= Ai <= 1e9) (1 <= i  <= N)

The third line contains a single number M denoting the number of question the girl want to ask you. (1 <= M <= 1e6)

The next M lines each contain two numbers; L R meaning that the question asks about the sum of uniqueness of the all tea that is in range index L to R. (1 <= L <= R <= N)

Output

M lines each contain a single number; Bj denoting the answer for the question j. 

Example

Input:
8 
3 5 6 2 4 5 7 1
5
1 3
2 4
2 5
1 8
4 7

Output:
0
2
4
13
0