Bạn được cho một mảng gồm \(n\) số nguyên và \(q\) truy vấn có dạng: có bao nhiêu giá trị khác nhau trong đoạn \([a,b]\)?

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\): kích thước mảng và số lượng truy vấn
• Dòng tiếp theo chứa \(n\) số nguyên \(x_1,x_2,...,x_n\): các giá trị của mảng
• Cuối cùng là \(q\) dòng mô tả các truy vấn. Mỗi dòng chứa hai số nguyên \(a\) và \(b\)

Constraints

• \(1 \leq n,q \leq 2\cdot 10^5\)
• \(1 \leq x_i \leq 10^9\)
• \(1 \leq a \leq b \leq n\)

Output

• Với mỗi truy vấn, in ra số lượng giá trị khác nhau trong đoạn

Example

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

2
3
3