І знову ж таки, запити

Вам надається масив цілих чисел $a_1,a_2,\dots ,a_n$ та ціле число $k$. Ваше завдання — відповісти на $q$ запитів такого типу:

• Для заданого $(l,r)$ вам потрібно розділити підмасив $[a_l,a_{l+1},\dots ,a_r]$ на мінімальну кількість послідовних підвідрізків так, щоб кількість різних цілих чисел в кожному підвідрізку була не більше $k$. Кожен елемент від $l$ до $r$ належить рівно одному підвідрізку.

Вхідні дані

Перший рядок містить три цілі числа $n$, $k$, $q$ $(1\le n,q\le 3\cdot 10^5;1\le k\le n)$ — довжина $a$, фіксоване $k$ для кожного запиту та кількість запитів, відповідно.

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ $(1\le a_i\le 10^9)$ — елементи $a$.

Кожен з наступних $q$ рядків містить два цілі числа $l$ та $r$ $(1\le l\le r\le n)$, що описують запит.

Вихідні дані

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

Приклади

Примітка

У першому прикладі є $5$ запитів.

1. $l=1$, $r=3$. Ми повинні розділити $[a_1,a_2,a_3]=[1,4,2]$. Одним з можливих розподілів є $[1],[4,2]$. У перший підвідрізок містить одне число, а другий — два різних числа. Зверніть увагу, що розбиття $[1,4,2]$ є неправильним, оскільки цей підвідрізок містить три різних числа, тоді як $k=2$;

2. $l=1,r=5$. Ми повинні розділити $[1,4,2,4,1]$. Одним з можливих розподілів є $[1,4],[2],[4,1]$;

3. $l=2,r=4$. Ми повинні розділити $[4,2,4]$. Одним з можливих розподілів є $[4,2,4]$;

4. $l=3,r=4$. Ми повинні розділити $[2,4]$. Одним з можливих розподілів є $[2,4]$;

5. $l=2,r=5$. Ми повинні розділити $[4,2,4,1]$. Одним з можливих розподілів є $[4,2],[4,1]$.

Оцінювання

1. ($3$ бали): $q=1$ та $l=1,r=n$;

2. ($8$ балів): $k=1$;

3. ($14$ балів): $l=1$ для всіх запитів;

4. ($22$ бали): $a_i\le 10^5,n\le 10^5$;

5. ($28$ балів): $a_i\le 10^5$;

6. ($25$ балів): без додаткових обмежень.