Problem
Có một dãy số tự nhiên a
1, a
2, ..., a
n. Hãy xem xét một số mảng con của nó a
l, a
l + 1, ..., a
r, trong đó 1 ≤ l ≤ r ≤ n, và với mỗi số tự nhiên s biểu thị bằng K
s số lần xuất hiện của các số s trong mảng con này. Hãy gọi số lượng của một mảng con là tổng của các tích K
s·K
s·s trên tất cả các số nguyên phân biệt s. Vì số lượng các số khác nhau trong mảng là hữu hạn nên tổng chỉ chứa một số hữu hạn các số hạng khác 0.
Cần phải tính toán lực lượng của từng mảng con trong số t mảng con đã cho.
Đầu vào
Dòng đầu tiên chứa hai số nguyên n và t (1 ≤ n, t ≤ 200000) — tương ứng là độ dài của mảng và số lượng yêu cầu.
Dòng thứ hai chứa n số tự nhiên ai (1 ≤ a
i ≤ 10
6) — phần tử mảng.
T dòng tiếp theo chứa hai số nguyên dương l và r (1 ≤ l ≤ r ≤ n) — các chỉ mục của đầu bên trái và bên phải của mảng con tương ứng.
Dấu ấn
In t dòng, trong đó dòng thứ i chứa số tự nhiên duy nhất — lực lượng của mảng con truy vấn thứ i.
Ví dụ:
| Đầu vào |
Đầu ra |
3 2
1 2 1
1 2
1 3
| 3
6 |
8 3
1 1 2 2 1 3 1 1
27
16
27 |
20
20
20 |