All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Everybody knows, that five is an extremely lucky number. It's even more lucky than seven!
For instance, five is widely used in Chinese culture. The famous Chinese Five Elements refer to Gold, Wood, Water, Fire and Earth, which are regarded as the basis of the whole world. In folklore, Chinese people hold the mutual restriction of the five elements: “wood restricting earth, earth restricting water, water restricting fire, fire restricting gold and gold restricting wood”. This mutual restriction principle is seriously stressed by the ancient Chinese people to show that everything in the world is mutually affected.
You see how important the number is? That's why this number will be under our consideration in this problem!
You are given a sequence a1, a2, ..., aN of non-negative integers. Your task is to process Q queries of the following format: each query is described by two integers L ≤ R and asks to calculate the number of triples (i, j, k), such that L < i < j < k < R and aL > ai < aj > ak < aR.
The first line of the input contains two integers N and Q denoting the size of the sequence and the number of the queries to process.
The second line contains N non-negative integers a1, a2, ..., aN.
Each of the next Q lines contains two integers L and R describing the corresponding query.
For each query, output a single line containing one integers: the number of triples as described above.
- 1 ≤ N ≤ 2000
- 1 ≤ Q ≤ 100000
- 0 ≤ ai ≤ 109
- 1 ≤ L ≤ R ≤ N for each query in the input
Input: 10 3 5 5 1 1 5 5 1 1 5 5 1 10 2 9 1 1 Output: 8 8 0
The following triples(i, j, k) are valid for the first and the second queries:
- (3, 5, 7)
- (3, 5, 8)
- (3, 6, 7)
- (3, 6, 8)
- (4, 5, 7)
- (4, 5, 8)
- (4, 6, 7)
- (4, 6, 8)
|Tags||cook57, dynamic-programming, fenwick, kostya_by, medium|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.