区间最值（ST算法）
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
输入一串数字，给你M个询问，每次询问给你两个数字X，Y，要求你说出X到Y这段区间内的最大数。
输入格式
第一行两个整数N，M(1≤N≤10^5, 1≤M≤10^6)，表示数字的个数和要询问的次数；
接下来一行为N个数；
接下来M行，每行都有两个整数X，Y(1≤X≤Y≤N)。
数列和不超过2^31-1。
输出格式
输出共M行，每行输出一个数。
输入/输出样例
10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8
5
8
说明/提示
时间1000ms，内存256MiB