如果一个序列不包含三个连续元素x，y，z，使得x≥y≥z，那么它几乎是递增的。 
您将得到一个数组a1、a2、…、an和q的查询。 
每个查询包含两个整数l和r，1≤l≤r≤n。对于每个查询，找到子数组al，al+1，…，ar的最长几乎递增子序列的长度。 
子序列是一个序列，可以通过删除零个或多个元素而不改变保留元素的顺序来从给定序列中导出。

第一行输入包含两个整数，n和q（1≤n，q≤30000）—— 数组的长度和查询的数量。 
第二行包含n个整数a1，a2，…，an（1≤ai≤10⁹）—— 数组a的值。 
接下来的q行中的每一行都包含一个查询的描述。每行包含两个整数l和r（1≤l≤r≤n）——查询是关于子数组al，al+1，…，ar。

对于每个q个查询，打印一行，其中包含子数组al，al+1，…，ar的最长几乎递增子序列的长度。