#4491. 我也不知道题目名字是什么

题目描述

给定一个序列A[i]，每次询问l,r，求[l,r]内最长子串，使得该子串为不上升子串或不下降子串

输入格式

第一行n，表示A数组有多少元素

接下来一行为n个整数A[i]

接下来一个整数Q，表示询问数量

接下来Q行，每行2个整数l，r

N,Q<=50000

输出格式

对于每个询问，求[l,r]内最长子串，使得该子串为不上升子串或不下降子串

样例

样例输入

9  

1 2 3 4 5 6 5 4 3  

5  

1 6  

1 7  

2 7  

1 9  

5 9

样例输出

6  

6  

5  

6  

4  

//样例解释  

五个询问分别对应  

[1,6][1,6][2,6][1,6][6,9]

数据范围与提示