从技术上讲,这是一个交互问题。
一个包含 $$$m$$$ 数字的数组 $$$a$$$ 被称为 可整除 如果至少满足以下条件之一:
- 存在一个索引 $$$i$$$ ($$$1 \le i \lt m$$$) 和一个整数 $$$x$$$,这样对于所有索引 $$$j$$$ ($$$j \le i$$$),它认为 $$$a_{j} \le x$$$ 对于所有索引 $$$k$$$ ($$$k \gt i$$$),它认为$$$a_{k} \gt x$$$。
- 存在一个索引 $$$i$$$ ($$$1 \le i \lt m$$$) 和一个整数 $$$x$$$,这样对于所有索引 $$$j$$$ ($$$j \le i$$$),它保持 $$$a_{j} \gt x$$$ 并且对于所有索引 $$$k$$$ ($$$k \gt i$$$),它保持$$$a_{k} \le x$$$。
给你一个整数 $$$1, 2, \dots, n$$$ 的排列 $$$p$$$。你的任务是快速回答以下形式的查询:如果我们只从排列中取出段 [$$$l$$$, $$$r$$$],即数字 $$$p_{l}, p_{l + 1}, \dots, p_{r}$$$,就是这个数字子数组 可整除?
查询将以交互模式以 $$$10$$$ 为一组提交,这意味着在输出当前组的所有答案之前,您将不会收到下一组查询。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^{5}$$$) — 排列的大小。
第二行包含 $$$n$$$ 整数 $$$p_{i}$$$ ($$$1 \le p_{i} \le n$$$) — 自然数本身的排列。
第三行包含一个整数 $$$q$$$ ($$$10 \le q \le 10^{6}, q \bmod 10 = 0$$$) — 查询数量。
以下 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \lt r \le n$$$) — 查询的参数。
输出
对于每个查询,输出字符串“是"如果此查询的子数组是 可整除 和“NO”否则。
打印一组查询的答案后,不要忘记输出行尾并刷新输出缓冲区。否则,您可能会得到 超出空闲限制 判决。要刷新缓冲区,请使用:
- fflush(标准输出) or cout.flush() in C++;
- System.out.flush() in Java;
- 冲洗(输出) in 帕斯卡;
- stdout.flush() in Python;
- 请参阅其他语言的文档。
您必须在第 $$$10$$$、第 $$$20$$$、第 $$$30$$$ 查询(依此类推)之后刷新输出缓冲区,i。 e.在索引可被 $$$10$$$ 整除的每个查询之后。之后,您可以阅读下一组查询。
示例
输入复制
74 2 3 6 1 5 7201 21 31 41 51 62 32 42 52 63 43 53 64 54 65 61 72 73 74 75 7
输出复制
YES YES YES YES NO YES YES YES NO YES YES NO YES YES YES YES YES YES YES YES