# And Again, Queries

You are given an array of integers $a_{1},a_{2},…,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},…,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≤n,q≤3⋅10_{5};1≤k≤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},…,a_{n}$ $(1≤a_{i}≤10_{9})$ — elements of $a$.

Each of the following $q$ lines contains two integers $l$ and $r$ $(1≤l≤r≤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.

$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$;

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

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

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

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

## Scoring

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

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

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

($22$ points): $a_{i}≤10_{5},n≤10_{5}$;

($28$ points): $a_{i}≤10_{5}$;

($25$ points): no additional restrictions.