同学们在实验室玩游戏，每个人有一个兴奋值 aia_iai ，但是这时候教练走过来了。教练有多次询问，每次会询问在一个区间的最大兴奋值。每个询问会影响在当前询问区间 $[l,r]$ 内的人的兴奋值，只影响这次询问，每个人的兴奋值会因为这次询问变成 min(ai,i−l+1)min(a_i,i - l + 1)min(ai,i−l+1) 。

第一行两个整数 $n$ 和 $m$  ( 1≤n,m≤1051 \le n,m \le 10^ 51≤n,m≤10⁵) 分别代表学生个数和询问个数。
第二行有 $n$ 个整数，第 $i$ 个整数为 aia_iai ( 1≤ai≤1051 \le a_i \le 10^51≤ai≤10⁵ ) ,下标 $i$ 从1开始。
第三行到第 $m+2$ 行每行有一个两个整数 $l,r$ ( $1\le l\le r\le n$ )。

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

第一个询问 $[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$。

 2022河南萌新联赛第（一）场：河南工业大学