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\).

Output

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

Giới hạn

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

Ví dụ

Input

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

Output

2
3
3