题目描述

管家记录了 $n$ 笔账目，每笔有一个金额。财主会提出 $m$ 个查询，每个查询给出一个区间 $[a, b]$，要求找出该区间内金额最少的那笔账目。

输入格式

第一行两个整数 $n$ 和 $m$。

第二行 $n$ 个整数，表示每笔账目的金额。

接下来 $m$ 行，每行两个整数 $a$ 和 $b$，表示查询区间。

输出格式

一行 $m$ 个整数，用空格分隔，表示每个查询的答案。

样例

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

2 3 1

提示

$1 \le n, m \le 10^5$，$0 \le x_i \le 10^5$