Tại trung tâm sơ chế và đóng gói nông sản xoài tròn Yên Châu, các kiện hàng xoài xuất khẩu được đánh số từ ~1~ đến ~N~ theo thứ tự vận chuyển trên băng chuyền thông minh. Mỗi kiện hàng ~i~ ~(1 \le i \le N)~ có một chỉ số tiêu chuẩn chất lượng là số nguyên dương ~A_i~.

Để kiểm soát sự sai lệch trình tự đóng gói trong quá trình phân loại tự động, hệ thống quản lý logistics cần thực hiện ~Q~ đợt kiểm tra độc lập. Mỗi đợt kiểm tra được xác định bởi hai mốc vị trí ~L~ và ~R~ ~(1 \le L \le R \le N)~. Trong đoạn từ kiện hàng thứ ~L~ đến kiện hàng thứ ~R~, hệ thống cần xác định độ xáo trộn của chuỗi cung ứng bằng cách đếm số lượng cặp kiện hàng ~(i, j)~ xảy ra hiện tượng đảo ngược chất lượng, tức là: ~L \le i < j \le R~ và ~A_i > A_j~.

Hãy giúp ban quản lý tính toán số cặp đảo ngược chất lượng cho từng đợt kiểm tra.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~Q~ ~(1 \le N, Q \le 5 \cdot 10^4)~;

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ ~(1 \le A_i \le 10^9)~;

• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L~ và ~R~ ~(1 \le L \le R \le N)~ mô tả một truy vấn.

Output

Gồm ~Q~ dòng, mỗi dòng một số nguyên là số cặp đảo ngược chất lượng tìm được trong đoạn tương ứng.

Scoring

Sample Input 1

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

Sample Output 1

3
1
3

Notes

• Truy vấn ~1~ ~(L = 1, R = 4)~: Dãy chỉ số tiêu chuẩn chất lượng là ~[3, 1, 4, 2]~. Có ~3~ cặp đảo ngược chất lượng;

• Truy vấn ~2~ ~(L = 2, R = 5)~: Dãy chỉ số tiêu chuẩn chất lượng là ~[1, 4, 2, 5]~. Có ~1~ cặp đảo ngược chất lượng;

• Truy vấn ~3~ ~(L = 1, R = 5)~: Dãy chỉ số tiêu chuẩn chất lượng là ~[3, 1, 4, 2, 5]~. Có ~3~ cặp đảo ngược chất lượng.