Lucky Fives

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 a_{1}, a_{2}, ..., a_{N} of nonnegative 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 a_{L} > a_{i} < a_{j} > a_{k} < a_{R}.
Input
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 nonnegative integers a_{1}, a_{2}, ..., a_{N}.
Each of the next Q lines contains two integers L and R describing the corresponding query.
Output
For each query, output a single line containing one integers: the number of triples as described above.
Constraints
 1 ≤ N ≤ 2000
 1 ≤ Q ≤ 100000
 0 ≤ a_{i} ≤ 10^{9}
 1 ≤ L ≤ R ≤ N for each query in the input
Example
Input: 10 3 5 5 1 1 5 5 1 1 5 5 1 10 2 9 1 1 Output: 8 8 0
Explanation
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)
Author:  kostya_by 
Tester:  stzgd 
Editorial  http://discuss.codechef.com/problems/LFIVES 
Tags  cook57, dynamicprogramming, fenwick, kostya_by, medium 
Date Added:  10052014 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 