时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
五门是空洞骑士中最难的有成就的挑战，在五门中，玩家将与这个游戏中出现的所有的boss进行车轮战，boss的出场顺序是固定的，这是对操作和耐力的极大考验，经过长达三个小时的奋斗，马子哥对每一个boss的难度都有了一个整数评级
，数值越大难度越高。
“已经没有什么好害怕的了，感觉身体好轻”——马子哥如是说。
马子哥的自信来自于他刚刚下载的风灵月影修改器，有了这个修改器他可以肆意修改游戏，作为一个卡在“空洞骑士”五门长达3h的菜鸡，他认为有了这个修改器他就可以无所畏惧。具体来说，使用这个修改器，他可以跳过一连串连续出场的BOSS。
但是马子哥的自尊心开始作祟，他给自己的修仙行为加了限制——在跳过一串连续的boss时，他必须要从难度最高的boss或最先出现的boss中选择一个加以保留（其余的boss将被删去），若有多个难度最高的BOSS，马子哥可以随意决定哪个会被留下来。修改后被跳过的boss不会再出现，其它被保留的boss出场的相对顺序仍然不变
例如说，现在有一串BOSS，战力值分别是（10,20,30,40,50,60），马子哥可以选择区间[2,5]，在这个区间上作弊，他需要选择保留这个区间内的第一个BOSS（20）或者是战力值最高的BOSS(50)，剩下的删除。所以最终会有两种新BOSS序列：1.(10,20,60) 2.(10,50,60)
糟了，这样限制马子哥还是打不过五门！那他只能再加一个条件——他可以多次执行这个作弊操作，每次在上次修改后生成的新的boss序列中修改
由于实力不济，马子哥暂时想着先分段练习，因此，他会把五门中的一段连续的BOSS截下来单独挑战，当然，他也会用修改器辅助这段练习。（此时，我们视作五门里只有这些BOSS，具体可以参考样例）
现在马子哥想问问你，按他这个修改法，对于每一个练习段，如果最后修改到只剩下一个boss，可能出现的不同boss的数量。（不同boss：指在原序列中下标不同的BOSS，例如，(10,10)中两个战力相同的BOSS是两个不同的BOSS）
输入描述:
第一行两个整数
,代表五门的BOSS个数与练习的段数
第二行n个正整数
，代表五门每个BOSS的战力
第2+i至2+T行，每行有两个正整数
，马子哥要在
这个区间内进行练习
输出描述:
一共T行，每行一个正整数ans,代表对于这段练习，这个区间可能可以被留下来的数字有多少个
示例2
备注:
样例解释：
1. 第一段练习的战力数组为B[1..3]，即{2,4,3}，2 4 3均可以通过合理布置操作使他们成为最后一个留下来的BOSS
2. 第二段练习的战力数组为B[3..5]，即{3,5,1}，3 5均可以通过合理布置操作使他们成为最后一个留下来的BOSS
第一段练习的3可以通过如下方式保留：
1) {2,4,3}选择区间[1,2]，进行第一种操作，数组剩下{2,3}
2) {2,3}选择区间[1,2]，进行第二种操作，数组剩下{3}
数组为{3}，只剩下一个数，操作结束。所以3可以剩下来