#4358. permu

permu

题目描述

给出一个长度为 nn 的排列 pp

再给出 mm 个询问,每次询问某个区间 [l,r][l,r] 中,最长的值域连续段长度。

输入格式

第一行两个整数 n,mn,m,分别表示排列的长度和询问的次数。

第二行 nn 个整数 p1,p2,,pnp_1,p_2,\cdots,p_n,表示这个排列。

接下来 mm 行,每行两个整数 l,rl,r,表示询问的区间。

输出格式

对于每次询问,一行一个整数,表示答案。

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

提示

  • 对于询问 [1,4][1,4]p2,p4,p1p_2,p_4,p_1 组成最长的值域连续段为 [1,3][1,3]
  • 对于询问 [5,8][5,8]p8,p5,p7p_8,p_5,p_7 组成最长的值域连续段为 [4,6][4,6]
  • 对于询问 [1,7][1,7]p5,p7,p3,p6p_5,p_7,p_3,p_6 组成最长的值域连续段为 [5,8][5,8]

对于 100%100\% 的数据,1n,m5×1041\le n,m\le 5\times 10^4

题目来源

By sumix173\texttt{By sumix173}