Tý cần giải bài toán sau:

Trong một lớp học, giáo viên xếp \(N\) học sinh thành một hàng dọc và ghi lại chiều cao của từng học sinh (đơn vị cm). Một cặp học sinh được gọi là "lộn xộn" nếu học sinh đứng trước có chiều cao lớn hơn học sinh đứng sau. Giáo viên muốn thực hiện \(Q\) truy vấn, mỗi truy vấn yêu cầu đếm số cặp lộn xộn trong đoạn học sinh từ vị trí \(L\) đến vị trí \(R\).

Hãy viết chương trình giúp giáo viên giải quyết vấn đề này.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) — chiều cao của các học sinh (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L, R\) (\(1 \le L \le R \le N\)).

Định dạng đầu ra

• In ra \(Q\) dòng, mỗi dòng là số cặp lộn xộn trong đoạn tương ứng.

Ví dụ

Input:

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

Output:

2
3
7

Giải thích:

• \([1,3]\): \((5,3), (5,4)\) — 2 cặp.
• \([2,5]\): \((3,1), (4,1), (4,2)\) — 3 cặp.
• \([1,5]\): 7 cặp lộn xộn.

Subtask