Дано масив із \(n\) цілих чисел. Потрібно відповісти на \(q\) запитів. Для кожного запиту задано два числа \(l\) та \(r\). Знайдіть кількість різних значень на відрізку \(\left[l, r\right]\)

Input Specification

Перший рядок містить два числа \(n\) і \(q\) Другий рядок містить: \(a_1 a_2 ... a_n\) Наступні \(q\) рядків містять по два числа: \(l\) \(r\) \(\\1 \leq n \leq 5000\) \(\\1 \leq q \leq 5000\\\) \(-10^9 \leq a_i \leq 10^9\\\) \(1 \leq l \leq r \leq n\\\)

Output Specification

Для кожного запиту виведіть кількість різних значень на відрізку.

Sample Input 1

9 4
1 1 2 3 4 4 5 6 7
1 4
3 5
1 7
1 9

Sample Output 1

3
3
5
7

Sample Input 2

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

Sample Output 2

4
3
3