Loli là một học sinh bình thường ở "Trường THPT Bình Thường". Về phần học hành, có lúc Loli try hard, có lúc lại chill chill, làm những thứ thỏa mãn đam mê. Loli đã học ở trường này ~n~ tuần. Mỗi tuần đều có một bài kiểm tra; Điểm kiểm tra của Loli tại tuần thứ ~i~ là một số nguyên không âm ~a_i~.

Loli muốn phân tích "phong độ" của mình tại những khoảng thời gian khác nhau. Ta định nghĩa khoảng thời gian ~[L;R]~ bắt đầu từ tuần thứ ~L~ và kết thúc ở tuần thứ ~R~. Loli xác định liệu phong độ trong khoảng thời gian ~[L;R]~ có phập phù hay không bằng ~P~, được tính như sau:

1. Viết ra toàn bộ điểm từ tuần thứ ~L~ tới tuần thứ ~R~, sau đó sắp xếp dãy đó theo thứ tự tăng dần. Gọi dãy điểm đó là ~S~.

2. Tính tổng ~P = (S_2 - S_1)^2 + (S_3 - S_2)^2 + \dots + (S_{R-L+1} - S_{R-L})^2~.

Yêu cầu: Cho dãy điểm của Loli và những khoảng thời gian cần phân tích, hãy xác định ~P~ của mỗi khoảng thời gian.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, m~ ~(1\le n, m \le 5\times 10^4)~;

• Dòng tiếp theo chứa ~n~ số nguyên ~a_i~ ~(0\le a_i \le 10^6)~;

• ~m~ dòng còn lại, mỗi dòng chứa khoảng thời gian có dạng ~L\ R~ ~(1 \le L \le R \le n)~.

Output

Gồm ~m~ dòng, dòng ~j~ chứa kết quả tương ứng của khoảng thời gian ~j~.

Scoring

• Subtask 1 (20%): ~n, m\le 200~.

• Subtask 2 (20%): ~n, m\le 5\times10^3~.

• Subtask 3 (20%): ~0\le a_i \le 100~.

• Subtask 4 (40%): Không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

3
5
4
2
0

Notes

Trong ví dụ trên:

• Với khoảng thời gian ~[1,4]~: Dãy ~S = [1,2,3,4]~, nên ta có ~P = (2-1)^2 + (3-2)^2 + (4-3)^2 = 3~.

• Với khoảng thời gian ~[3,5]~: Dãy ~S = [2,4,5]~, nên ta có ~P = (4-2)^2 + (5-4)^2 = 5~.