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

Background

在一款科幻题材的游戏中，玩家的核心装备有 n 个连续的强化阶段（阶段编号 1~n）。每个强化阶段都有一个 “稳定值”—— 稳定值越高，该阶段强化时装备损坏的概率越低；反之则风险越高。 玩家在规划强化策略时，需要参考连续强化阶段的 “安全底线”：对于任意一段连续的强化区间 [L, R]，这段区间的 “安全阈值” 等于该区间内所有阶段的最低稳定值（最低稳定值决定了整个连续强化过程的风险上限）。 现在给出 n 个阶段的稳定值，以及 q 次查询请求。每次查询会指定一个强化区间 [L, R]，请你快速计算该区间的安全阈值，帮助玩家判断是否适合连续强化。

Format

Input

第一行包含两个正整数 n 和 q，分别代表强化阶段总数和查询次数。 第二行包含 n 个整数，第 i 个整数 s[i] 代表第 i 阶段的稳定值（稳定值为正整数，数值越大表示越稳定）。 接下来 q 行，每行包含两个正整数 L 和 R，代表查询的强化阶段区间（1≤L≤R≤n）。

Output

共 q 行，每行输出一个整数，对应查询区间 [L, R] 的安全阈值（即区间内的最低稳定值）。

Samples

8 5
32 17 25 41 19 37 22 29
1 4
3 7
2 5
6 8
1 8

17
19
17
22
17

Limitation

1s, 1024KiB for each test case.

数据规模与约定 1 ≤ n ≤ 1e5（强化阶段总数不超过 10 万）； 1 ≤ q ≤ 1e5（查询次数不超过 10 万）； 1 ≤ s [i] ≤ 1e9（稳定值为正整数，无负数）； 强化阶段的稳定值固定不变。