Cho dãy n số nguyên dương \(a_1, a_2, ... , a_n\). Một dãy con \((i,j)\) là dãy \(a_i , a_{i+1}, ... , a_j (1 \le i \le j \le n)\).

Với mỗi số nguyên dương \(s\) đặt \(K_s\) là số lần \(s\) xuất hiện trong dãy con \((i,j)\). Ta định nghĩa giá trị của dãy cọn \((i,j)\) là tổng:

Yêu cầu: Cho biết trước dãy \(a_1, a_2, ... , a_n\). Hãy trả lời \(m\) truy vấn, mỗi truy vấn có dạng hai số nguyên \(L, R (1 \le L \le R \le n)\) với yêu cầu tính giá trị của dãy con \(a_L , a_{L+1}, ... , a_R\)

Input

• Dòng 1: Chứa hai số nguyên dương \(n, m (1 \le n, m \le 2 \times 10^5)\)
• Dòng 2: Chứa \(n\) số nguyên \(a_1, a_2, ... , a_n (1 \le a_i \le 10^9 )\)
• Dòng 3 ...\(2+m\): Dòng \(2 + i\) chứa hai số nguyên \(L_i, R_i (1 \le L_i, R_i \le n)\) mô tả truy vấn thứ \(i (i = 1 ÷ m)\)

Output

• In ra \(m\) dòng, mỗi dòng một số nguyên là kết quả của một truy vấn (theo thứ tự xuất hiện trọng input)

Example

3 2
1 2 1
1 2
1 3

3
6

8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7

20
20
20