BOBAINV - Boba Inversion


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

hide comments
Rafail Loizou: 2023-08-20 04:49:34

Comments here are a bit misleading. If your O(N^2 * logN) solution doesn't pass instead of spending time trying to optimize it unnecessarily try to find a solution of better complexity.

sleepntsheep: 2023-04-22 13:34:13

O(N^2 logn) TLE :(

tropo_sphere: 2021-06-13 21:24:46

fast i/o would work

vas14: 2020-05-19 18:23:56

Straightforward N^2 solution TLE in C++ 14 but AC in gcc 4.3.2. Seems that I/O efficiency is the determining factor.

e_coder: 2020-05-14 19:53:21

@Autoratch: With the same time complexity, AC in C++ but TLE in JAVA

Vipul Srivastava: 2020-04-03 22:09:22

very nice problem!!


Added by:Autoratch
Date:2020-03-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All