本题无法使用主席树来做

本题无法使用主席树来做

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

\(mex\)是一个作用在集合上的函数,\(mex(S)\)表示不在集合\(S\)中的最小非负整数。
现在我们有一个长度为\(n\)的序列和\(Q\)个询问,每个询问查询序列中一段区间内的数组成的集合的\(mex\)值。

Format

Input

每个测试点仅包含一组输入数据。
第一行一个正整数\(n(n<=1000000)\)。
接下来一行\(n\)个整数,第\(i\)个整数\(a_i(0<=a_i<=1000000)\)表示序列的第\(i\)个数。
接下来一行一个正整数\(Q(Q<=1000000)\)。
接下来\(Q\)行,每行两个整数\(l,r(1<=l<=r<=n)\),表示查询序列第\(l\)个数到第\(r\)个数所组成集合的\(mex\)值。

Output

依照输入顺序,对于每组询问输出一行一个整数表示答案。

Sample 1

Input

10
2 0 1 3 0 0 2 4 7 1
7
1 2
5 6
5 10
1 3
1 5
6 6
7 8

Output

1
1
3
3
4
1
0

Limitation

4s, 1GB for each test case.

Source

Vijos Original

厦大附中模拟赛第四场

未参加
状态
已结束
规则
ACM/ICPC
题目
3
开始于
2021-01-17 14:00
结束于
2021-01-17 17:00
持续时间
3.0 小时
主持人
参赛人数
12