Cho dãy số \(A\) gồm \(N\) phần tử gồm các số nguyên dương \(A_1, A_2, ..., A_N\), và \(Q\) truy vấn, truy vấn thứ \(i\) gồm \(2\) số nguyên dương \(L_i, R_i\) \((1 \leq L_i \leq R_i \leq N)\).

Yêu cầu: Với mỗi truy vấn thứ \(i\), hãy đếm số phần tử phân biệt trong khoảng từ \(L_i\) tới \(R_i\).

Input

• Gồm \(Q+2\) dòng:
• Dòng thứ nhất chứa hai số nguyên dương \(N, Q\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((1 \leq A_i \leq 10^6)\).
• \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(L_i, R_i\).

Output

• In ra \(Q\) dòng, dòng thứ \(i\) là số phần tử phân biệt trong khoảng từ \(L_i\) tới \(R_i\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N, Q \leq 10^5\).

Example

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

3
2
3