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
vas14:
20200519 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:
20200514 19:53:21
@Autoratch: With the same time complexity, AC in C++ but TLE in JAVA 

Vipul Srivastava:
20200403 22:09:22
very nice problem!! 
Added by:  Autoratch 
Date:  20200329 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 