Bạn được cho một hoán vị ~P~ gồm ~N~ phần tử. Dựng một đồ thị vô hướng không trọng số gồm ~N~ đỉnh sao cho: tồn tại cạnh nối từ ~i~ đến ~j~ nếu như ~(i-j)\times (P_i-P_j)<0~. Bạn được cho ~Q~ truy vấn, mỗi truy vấn gồm ba số nguyên dương ~u,l,r~. Nhiệm vụ của bạn là với mỗi truy vấn, hãy tính tổng các giá trị ~D(u,v)~ thỏa mãn ~l\le D(u,v)\le r~ với mọi ~v~ từ ~1~ đến ~n~.

Trong đó, ~D(u,v)~ là độ dài đường đi ngắn nhất từ ~u~ đến ~v~, ~D(u,v)=+\infty~ nếu như không tồn tại đường đi từ ~u~ đến ~v~.

Input

Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~Q~ tương ứng với số lượng phần tử của hoán vị ~P~ và số lượng truy vấn (~1\le N,Q\le 10^5~).

Dòng thứ hai gồm ~N~ số nguyên dương ~P_1,P_2,\dots,P_N~ (~1\le P_i\le N~). Dữ liệu đảm bảo các giá trị ~P_i~ đôi một phân biệt.

Cuối cùng là ~Q~ dòng, mỗi dòng gồm ba số nguyên dương ~u,l,r~ mô tả các truy vấn (~1\le l\le r\le N,1\le u\le N~).

Output

Với mỗi truy vấn, in ra kết quả trên một dòng tương ứng với kết quả của truy vấn đó.

Scoring

Sample Input 1

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

Sample Output 1

3
5