Đếm cặp nghịch thế theo đoạn

Cho dãy số nguyên \(A_1, A_2, \dots, A_N\). Một cặp chỉ số \((i, j)\) được gọi là nghịch thế nếu \(i < j\) và \(A_i > A_j\).

Có \(Q\) truy vấn, mỗi truy vấn cho hai số \(L < R\). Với mỗi truy vấn, hãy đếm số cặp nghịch thế \((i, j)\) chỉ xét trong đoạn con \(A_L, A_{L+1}, \dots, A_R\), tức là các cặp thoả \(L \le i < j \le R\) và \(A_i > A_j\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, \dots, A_N\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L\) và \(R\).

Output

In ra \(Q\) dòng, dòng thứ \(t\) là đáp án của truy vấn thứ \(t\).

Constraints

• \(2 \le N \le 1000\).
• \(0 \le A_i \le 10^6\).
• \(1 \le L < R \le N\).
• Một nửa số test có \(Q = 1\), \(L = 1\), \(R = N\); nửa còn lại có \(1 \le Q \le 20\).

Sample Input

6 3
4 1 3 2 5 2
1 4
2 6
1 6

Sample Output

4
3
7

Explanation

Với đoạn \([1, 4]\) là dãy \(4, 1, 3, 2\): các cặp nghịch thế là \((4,1), (4,3), (4,2), (3,2)\) nên có \(4\) cặp.