兴奋值
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

同学们在实验室玩游戏，每个人有一个兴奋值 a_i ，但是这时候教练走过来了。教练有多次询问，每次会询问在一个区间的最大兴奋值。每个询问会影响在当前询问区间 内的人的兴奋值，只影响这次询问，每个人的兴奋值会因为这次询问变成  。

输入描述:

第一行两个整数 n 和 m  ( ) 分别代表学生个数和询问个数。

第二行有 n 个整数，第 i 个整数为 a_i (  ) ,下标 i 从1开始。

第三行到第  行每行有一个两个整数 l,r (  )。

输出描述:

对于每个询问输出询问值，不同询问之间用空格分隔。
示例1

输入

复制 
6 4
5 4 6 5 5 3
3 4
2 2
1 5
3 5

输出

复制 
2 1 5 3

说明

第一个询问 [3，4] ，兴奋值变成了 min(6，1) = 1，min(5，2) = 2 ，所以查询答案为 2。

第二个询问 [2 ，2] ，兴奋值变成了 min(4，1) = 1 ，所以查询的答案为 1。

第三个询问 [1 ，5] ，兴奋值变成了 min(5，1) = 1，min(4，2) = 2，min(6，3) = 3，min(5，4) = 4，min(5，5) = 5 ，所以查询答案为 5。

第四个询问 [3 ，4] ，兴奋值变成了 min(6，1) = 1，min(5，2) = 2，min(5，3) = 3 ，所以查询答案为 3。