题目描述

萧薰儿是古国的公主，平时的一大爱好是采花。

今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。

花园足够大，容纳了 $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

数据范围与提示

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