琴

(instrument.cpp 1s/512MB)

题目描述

作为一名出色的调琴师，小 W 每天都需要练习若干曲目来维持他的琴感。由于厌烦了每天都要决定练什么曲目，他预先选了 $n$ 首曲目并将他们排成一列，第 $i$ 首曲目的难度为 $a_i(1\le a_i\le 50)$。小 W 打算借助这些排好了的曲目练习 $m$ 天，第 $i$ 天，他会选定一个区间 $[l_i,r_i]$，以难度从小到大的顺序练习这个区间里的每一首曲目。但是小 W 有一个独特的要求，那就是练习时相邻曲目的难度差不能超过 $1$，也就是说下一首曲目的难度必须等于上一首曲目或者是上一首曲目的难度 $+1$，如果练完某个曲子后的下一首曲子不能满足这个要求，那么他就会终止练习。你能告诉他每天会练习多少首曲目吗？

输入格式

第一行包含一个整数 $n$，表示小 W 预先选定的曲目数量。

接下来一行包含 $n$ 个整数 $a_1, a_2, ..., a_n$，表示每首曲目的难度。

接下来一行包含一个整数 $m$，表示小 W 练习的天数。

接下来 $m$ 行，每行包含两个整数 $l_i$ 和 $r_i$，表示第 $i$ 天选择的练习区间 $[l_i, r_i]$。

输出格式

对于每一天的练习，输出一个整数，表示小 W 能够练习的曲目数量。

输入输出样例 #1

输入 #1

3  
1 2 2  
2  
1 3  
1 2 

输出 #1

3  
2

输入输出样例 #2

输入 #2

4
2 3 5 6
3
1 2
2 4
3 4

输出 #2

2
1
2

数据范围

对于 $30$ 的数据，$n,m\le 10^3$。

另有 $20$ 的数据，$a_i\le 2$。

对于 $100$ 的数据，$1\le n,m\le 10^5,1\le a_i\le 50$。