Cho dãy số gồm \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\). Có \(Q\) truy vấn, mỗi truy vấn cho hai số nguyên \(l\) và \(r\) có ý nghĩa: đếm số cặp chỉ số \((i, j)\) sao cho \(l\le i, j\le r\) và \(a_i\) chia hết cho \(a_j\) (hai cặp chỉ số \((i, j)\) và \((j, i)\) là khác nhau).

Dữ liệu vào từ tệp văn bản CSCH.INP:

• Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(Q\) \((N, Q \le 10^5)\) là số lượng phần tử và số lượng truy vấn;
• Dòng thứ hai gồm \(N\) số nguyên dương \(a_i \ (a_i\le 10^5; \ 1\le i\le N)\) mô tả dãy số;
• \(Q\) dòng sau, mỗi dòng gồm hai số nguyên dương \(l\) và \(r\) \((1\le l\le r\le N)\) mô tả truy vấn.

Kết quả ghi ra tệp văn bản CSCH.OUT:

\(Q\) dòng, mỗi dòng gồm một số nguyên là kết quả của truy vấn tương ứng.

Ví dụ

Input

5 2
3 1 3 3 4
2 4
1 5

Output

7
15

Giải thích

Ở truy vấn đầu tiên có các cặp chỉ số thoả mãn là: \((2, 2), (3, 3), (4, 4), (3, 2), (4, 2), (3, 4), (4, 3)\)

Ràng buộc

• Có \(20\%\) số test ứng với \(20\%\) số điểm thoả mãn: \(N, Q \le 10^2\);
• \(15\%\) số test khác ứng với \(15\%\) số điểm thoả mãn: \(N \le 10^4; \ Q\le 10^2\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm thoả mãn: \(N \le 10^5; \ Q\le 10^2\);
• \(15\%\) số test khác ứng với \(15\%\) số điểm thoả mãn: dãy số \(a_1, a_2, \dots, a_N\) là hoán vị từ \(1\) đến \(N\);
• \(15\%\) số test khác ứng với \(15\%\) số điểm thoả mãn: \(l = 1\);
• \(15\%\) số test khác ứng với \(15\%\) số điểm không có ràng buộc gì thêm.

Cho dãy số gồm \(N\) phần tử \(a_1, a_2, \dots, a_N\) là một hoán vị của các số nguyên từ \(1\) đến \(N\). Dãy con của một dãy số là dãy số nhận được khi không xoá phần tử nào hoặc xoá nhiều phần tử khỏi dãy số đó. Một dãy số \(b_1, b_2, \dots, b_M\) được gọi là dãy số lượn sóng khi thoả mãn điều kiện sau: Với mọi \(i \ (1\le i\le M-1)\), nếu \(b_i \lt b_{i+1}\) thì \(b_{i+1} \gt b_{i+2}\); hoặc nếu \(b_i \gt b_{i+1}\) thì \(b_{i+1} \lt b_{i+2}\). Dãy số gồm không quá \(2\) phần tử cũng là dãy số lượn sóng.

Ta gọi \(f(x, l, r)\) là số lượng phần tử của dãy con lượn sóng dài nhất của dãy số \(a_l, a_{l+1}, \dots, a_r\) sao cho tất cả các phần tử có giá trị không lớn hơn \(x\).

Đặt \(h(x) = \sum^N_{l=1} \sum^N_{r=l} f(x, l, r)\). Hãy tính các giá trị của \(h(1), h(2), \dots, h(N)\).

Dữ liệu vào từ tệp văn bản DSLS.INP:

• Dòng đầu tiên chứa số nguyên \(N \ (2\le N\le 2\times 10^5)\);
• Dòng thứ hai chứa \(N\) số nguyên \(a_i \ (1\le i\le n)\) là hoán vị từ \(1\) đến \(N\).

Kết quả ghi ra tệp văn bản DSLS.OUT:

Ghi trên \(N\) dòng, dòng thứ \(i \ (1\le i\le N)\) ghi một số nguyên là giá trị của \(h(i)\).

Ví dụ

Input

4
1 3 4 2

Output

4
8
14
18

Giải thích

\(h(1) = 1 + 1 + 1 + 1 + 0 + 0 + 0 + 0 + 0 + 0 = 4\)

\(h(2) = 1 + 1 + 1 + 2 + 0 + 0 + 1 + 0 + 1 + 1 = 8\)

\(h(3) = 1 + 2 + 2 + 3 + 1 + 1 + 2 + 0 + 1 + 1 = 14\)

\(h(4) = 1 + 2 + 2 + 3 + 1 + 2 + 3 + 1 + 2 + 1 = 18\)

Ràng buộc

• Có \(20\%\) số test ứng với \(20\%\) số điểm thoả mãn: \(N\le 15\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm thoả mãn: \(N \le 100\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm thoả mãn: \(N \le 500\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm thoả mãn: \(N\le 5000\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm không có ràng buộc gì thêm.

Cho một đơn đồ thị liên thông, vô hướng, có trọng số gồm:

• \(N\) đỉnh - được đánh số từ \(1\) đến \(N\);
• \(M\) cạnh - cạnh \((u, v, c)\) mô tả đường đi hai chiều trực tiếp giữa hai đỉnh \(u\) và đỉnh \(v\), có chi phí là \(c\);
• \(K\) đỉnh đặc biệt, phân biệt có tính chất như sau: trên đường đi, khi ở một đỉnh đặc biệt có thể di chuyển đến một đỉnh đặc biết bất kỳ trước đó đã đi qua mà không mất chi phí.

Tìm đường đi có tổng chi phí nhỏ nhất đi qua toàn bộ các đỉnh đặc biệt (đường đi có thể xuất phát từ một đỉnh bất kì).

Dữ liệu vào từ tệp văn bản DDDB.INP:

• Dòng đầu tiên gồm ba số nguyên dương \(N, M\) và \(K \ (2\le K\le N; \ N, M\le 10^5)\) mô tả số lượng đỉnh, số lượng cạnh và số lượng đỉnh đặc biệt;
• Dòng thứ hai gồm \(K\) số nguyên dương \(S \ (S \le N)\) mô tả các đỉnh đặc biệt;
• \(M\) dòng sau, mỗi dòng gồm ba số nguyên dương \(u, v, c \ (u, v\le N; \ c\le 10^9)\) mô tả các cạnh của đồ thị.

Kết quả ghi ra tệp văn bản DDDB.OUT:

Một số nguyên duy nhất là tổng chi phí nhỏ nhất của đường đi thoả mãn yêu cầu.

Ví dụ

Input

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

Output

5

Giải thích

Có thể đi theo đường đi: \(4 \rightarrow 1 \rightarrow 2 \rightarrow 3\)

Input

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

Output

7

Giải thích

Có thể đi theo đường đi: \(1 \rightarrow 2 \rightarrow 3 \rightarrow 1\rightarrow 2\rightarrow 5\)

Ràng buộc

• Có \(20\%\) số test ứng với \(20\%\) số điểm thoả mãn: \(K=2; \ N\le 10^4\);
• \(15\%\) số test khác ứng với \(15\%\) số điểm thoả mãn: \(K=5; \ N\le 10^4\);
• \(15\%\) số test khác ứng với \(15\%\) số điểm thoả mãn: \(K=N\);
• \(15\%\) số test khác ứng với \(15\%\) số điểm thoả mãn: \(N, M\le 10^3\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm thoả mãn: \(M=N-1\);
• \(15\%\) số test khác ứng với \(15\%\) số điểm không có ràng buộc gì thêm.