QOJ.ac

QOJ

Time Limit: 0.5 s Memory Limit: 128 MB Total points: 100

# 4181. HH 的项链

Statistics

Time Limit: 1.5s → 0.5s

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH 不断地收集新的贝壳,因此他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答。。。因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。

输入格式

第一行:一个整数 $N$,表示项链的长度。

第二行:$N$ 个整数,表示依次表示项链中贝壳的编号(编号为 $0$ 到 $1\,000\,000$ 之间的整数)。

第三行:一个整数 $M$,表示 HH 询问的个数。

接下来 $M$ 行:每行两个整数,$L$ 和 $R$($1 \leq L \leq R \leq N$),表示询问的区间。

输出格式

$M$ 行,每行一个整数,依次表示询问对应的答案。

样例输入

6
1 2 3 4 3 5
3
1 2
3 5
2 6

样例输出

2
2
4

子任务

测试点 $N$ $M$
$1$ $100$ $100$
$2$ $1\,000$ $1\,000$
$3$ $2\,000$ $200\,000$
$4$ $3\,000$ $200\,000$
$5$ $30\,000$ $200\,000$
$6$ $40\,000$ $200\,000$
$7 \sim 10$ $50\,000$ $200\,000$

对于 $100\%$ 的数据,$1 \leq N \leq 50\,000, 1 \leq M \leq 200\,000$。