题目背景

园艺师小芸负责照料一片新建的花田。她有个特别的采收习惯：最后收进篮子的花里，任何一种颜色都不能只出现一次——要么不采这种颜色，要么至少采两朵。

题目描述

花田里种着 $n$ 朵花，排成一排，共有 $c$ 种颜色，用整数 $1 \sim c$ 表示。小芸每次只能采收连续的一段花。对于每一次采收区间，她实际会采走的花满足：该颜色在区间内至少出现两次（这样她就能把同色的花成对采走）；只出现一次的颜色她一朵也不会动。她想知道每次采收能拿到多少种不同颜色的花。

共有 $m$ 次采收计划，请对每次计划输出答案。

输入格式

输入的第一行是三个用空格隔开的整数，分别代表花的个数 $n$，花的颜色数 $c$，以及采收计划数 $m$。

输入的第二行是 $n$ 个用空格隔开的整数，第 $i$ 个整数代表第 $i$ 朵花的颜色 $x_i$。

第 $3$ 行到第 $(m + 2)$ 行，每行两个整数 $l, r$，第 $(i + 2)$ 行的数字代表第 $i$ 次采收为第 $l$ 到第 $r$ 朵花。

输出格式

共输出 $m$ 行，每行一个整数。第 $i$ 行的整数代表第 $i$ 次采收能采到的花共有几种不同的颜色。

样例

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

2
0
0
1
0

提示

输入输出样例 $1$ 解释

共有五朵花，颜色分别为 $1,~2,~2,~3,~1$。

对于第一次采收，区间为 $[1, 5]$，可以采位置 $1,~2,~3,~5$ 处的花，共有 $1$ 和 $2$ 两种不同的颜色。

对于第二次采收，区间为 $[1, 2]$，但是颜色为 $1$ 和 $2$ 的花都只出现了一次，因此无花可采。

对于第三次采收，区间为 $[2, 2]$，但是颜色为 $2$ 的花只出现了一次，无花可采。

对于第四次采收，区间为 $[2, 3]$，可以采 $2,~3$ 位置的花，只有 $2$ 这一种颜色。

对于第五次采收，区间为 $[3,5]$，但是颜色为 $1, 2, 3$ 的花都只出现了一次，无花可采。

数据范围与约定

对于全部数据，保证 $1 \leq n, c, m \leq 2 \times 10^6$，$1 \leq x_i \leq c$，$1 \leq l \leq r \leq n$。