permu

时间限制:30s      空间限制:512MB

题目描述

给出一个长度为n的排列P(P1,P2,...Pn),以及m个询问。每次询问某个区间[l,r]中,最长的值域
连续段长度。


输入格式

第一行两个整数n,m。
接下来一行n个整数,描述P。
接下来m行,每行两个整数l,r,描述一组询问。


输出格式

对于每组询问,输出一行一个整数,描述答案。


样例输入

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

样例输出

3
3
4

提示

对于询问[1,4],P2,P4,P1组成最长的值域连续段[1,3];
对于询问[5,8],P8,P5,P7组成最长的值域连续段[4,6];
对于询问[1,7],P5,P7,P3,P6组成最长的值域连续段[5,8]。
1<=n,m<=50000


题目来源

By sumix173