魔法
暂无测试数据。
小 Y 正在研究魔法。一个魔法是一个由正整数 $1 \sim d$ 组成的序列，长度任意。
一个魔法 A 如果是另一个魔法 B 的子序列，则称这个魔法 A 被魔法 B 包含 。
小 Z 给了小 Y 一个长度为 $n$ 的序列。每次给小 Y 两个数 $l,r$ ，表示一个区间 $[l,r]$ 所表示的魔法。小 Z 想知道，最短的不被该区间包含的魔法多长呢？
输入格式
第一行三个正整数数 $n,m,d$。表示序列的长度以及序列的值域。
接下来一行 $n$ 个正整数，表示了这个序列。
接下来 $m$ 行一行两个正整数 $l,r$。表示询问的区间。
输出格式
输出 $m$ 行。对于每一个询问输出一行一个正整数表示你的答案。
数据范围
共有 $20$ 个数据点，数据大小如下。
| 编号 | n | m | d |
|---|---|---|---|
| $1$ | $10$ | $10$ | $2$ |
| $2$ | $10$ | $10$ | $3$ |
| $3$ | $3000$ | $3000$ | $2$ |
| $4$ | $3000$ | $3000$ | $2$ |
| $5$ | $3000$ | $3000$ | $3$ |
| $6$ | $3000$ | $3000$ | $3$ |
| $7$ | $3000$ | $3000$ | $20$ |
| $8$ | $3000$ | $3000$ | $20$ |
| $9$ | $10^5$ | $10^5$ | $2$ |
| $10$ | $10^5$ | $10^5$ | $2$ |
| $11$ | $10^5$ | $10^5$ | $3$ |
| $12$ | $10^5$ | $10^5$ | $3$ |
| $13$ | $10^5$ | $10^5$ | $50$ |
| $14$ | $10^5$ | $10^5$ | $100$ |
| $15$ | $10^5$ | $10^5$ | $1000$ |
| $16$ | $2 \times 10^5$ | $2 \times 10^5$ | $5$ |
| $17$ | $2 \times 10^5$ | $2 \times 10^5$ | $100$ |
| $18$ | $5 \times 10^5$ | $5 \times 10^5$ | $5$ |
| $19$ | $5 \times 10^5$ | $5 \times 10^5$ | $20$ |
| $20$ | $5 \times 10^5$ | $5 \times 10^5$ | $100$ |
保证除 $n,m,d$ 外，其他数据纯随机。
保证存在不依赖数据随机性能通过的算法。
5 4 3
1 2 3 3 1
1 4
1 3
2 5
1 2
2
2
2
1