Cho mảng ~a~ với ~n~ phần tử được đánh số từ ~1~ đến ~n~.

Điểm lớn hơn của một số tại vị trí ~i~ là số các số vị trí ~j~ mà ~a_j > a_i~ với ~i > j ~.

Cho ~m~ truy vấn ~l~, ~r~, hay cho biết tổng các điểm lớn hơn của các số trong khoảng từ ~l~ đến ~r~ này.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n, m~ ~(1 \le n, m \le 10^5)~.

Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^6)~.

~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l~, ~r~ ~(1 \le l \le r \le n)~.

Output

Xuất ra ~m~ dòng, với mỗi dòng là câu trả lời tương ứng.

Simple Input

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

Simple Output

5
8
1