Cho dãy \(n\) số nguyên \(a_1, a_2, ... , a_n\) và \(m\) truy vấn. Mỗi truy vấn có dạng hai số nguyên \(u, v\) với ý
nghĩa đếm xem trong dãy con \(a_u, a_{u+1}, ... , a_v\) có bao nhiêu giá trị khác nhau mà các giá trị này
xuất hiện đúng hai lần?

Input

• Dòng đầu ghi hai số nguyên dương \(n, m (1 \le n, m \le 5 \times 10^5 )\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ... , a_n\) \((0 \le a_i \le 10^9 ∶ i = 1 ÷ n)\)

• \(m\) dòng cuối, mỗi dòng ghi hai số nguyên \(u, v\) mô tả một truy vấn.

Output

• Với mỗi truy vấn in ra một dòng một số nguyên - kết quả tìm được.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n, m \le 5000\)
• Subtask \(2\) (\(60\%\) số điểm): không có ràng buộc gì

Example

5 1
1 2 1 1 1
1 3

1