题目描述

乌拉乎家农场的 n (1 ≤ n ≤ 50000) 头牛总是按同一序列排队。 有一天, 乌拉乎决定让一些牛们玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛。但是为了避免水平悬殊，牛的身高不应该相差太大。乌拉乎准备进行 q (1 ≤ q ≤ 180000) 次询问，第 a 头牛到第 b 头牛中，最高和最矮的牛身高分别是多少 。

输入格式

若干行

第 1 行包含两个正整数 n，q。

第 2 行，n个整数 hi。

再接下来的q行，每行两个整数 a, b, 表示询问第 a 头牛到第 b 头牛中，最高和最矮的牛身高分别是多少。

输出格式

共 q 行，每行两个整数，表示魅族询问中，最高和最矮的牛的身高。

样例1

4 3
1 3 4 5
1 3
2 4
1 2

4 1
5 3
3 1

样例2

6 3
1 7 3 4 2 5
1 5
4 6
2 2

7 1  
5 2 
7 7

数据范围

1 ≤ n ≤ 50000; 1 ≤ q ≤ 180000; 1 ≤ hi ≤ 1000000。