And Again, Queries

You are given an array of integers $a_1,a_2,\dots ,a_n$ and an integer $k$. Your task is to answer $q$ queries of the type:

• For a given $(l,r)$, you must divide the subarray $[a_l,a_{l+1},\dots ,a_r]$ into the minimum number of contiguous segments so that the number of distinct integers in each segment is at most $k$. Each element from $l$ to $r$ belongs to exactly one segment.

Input

The first line contains three integers $n$, $k$, $q$ $(1\le n,q\le 3\cdot 10^5;1\le k\le n)$ — the length of $a$, the fixed $k$ for each query, and the number of queries, respectively.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ $(1\le a_i\le 10^9)$ — elements of $a$.

Each of the following $q$ lines contains two integers $l$ and $r$ $(1\le l\le r\le n)$ describing the query.

Output

For each query, output the minimum number of segments it may be divided.

Examples

Note

In the first example, there are $5$ queries.

1. $l=1$, $r=3$. We should divide $[a_1,a_2,a_3]=[1,4,2]$. One of the possible divisions is $[1],[4,2]$. The first segment has one distinct number and the second segment has two distinct numbers. Notice that the division $[1,4,2]$ is incorrect because this segment contains three distinct numbers while $k=2$;

2. $l=1,r=5$. We should divide $[1,4,2,4,1]$. A possible division is $[1,4],[2],[4,1]$;

3. $l=2,r=4$. We should divide $[4,2,4]$. A possible division is $[4,2,4]$;

4. $l=3,r=4$. We should divide $[2,4]$. A possible division is $[2,4]$;

5. $l=2,r=5$. We should divide $[4,2,4,1]$. A possible division is $[4,2],[4,1]$.

Scoring

1. ($3$ points): $q=1$ and $l=1,r=n$;

2. ($8$ points): $k=1$;

3. ($14$ points): $l=1$ for all queries;

4. ($22$ points): $a_i\le 10^5,n\le 10^5$;

5. ($28$ points): $a_i\le 10^5$;

6. ($25$ points): no additional restrictions.