作为一名出色的调琴师，小 W 每天都需要练习若干曲目来维持他的琴感。由于厌烦了每天都要决定练什么曲目，他预先选了n首曲目并将他们排成一列，第i首曲目的难度为ai(1≤ai≤50)。小 W 打算借助这些排好了的曲目练习m天，第i天，他会选定一个区间[li,ri]，以难度从小到大的顺序练习这个区间里的每一首曲目。
但是小 W 有一个独特的要求，那就是练习时相邻曲目的难度差不能超过1，也就是说下一首曲目的难度必须等于上一首曲目或者是上一首曲目的难度+1，如果练完某个曲子后的下一首曲子不能满足这个要求，那么他就会终止练习。你能告诉他每天会练习多少首曲目吗？
第一行包含一个整数 n，表示小 W 预先选定的曲目数量。
接下来一行包含 n 个整数a1,a2,...,an，表示每首曲目的难度。
接下来一行包含一个整数m，表示小 W 练习的天数。
接下来m行，每行包含两个整数li和ri，表示第i天选择的练习区间[li,ri]。
样例1
3
1 2 2
2
1 3
1 2
样例2
4
2 3 5 6
3
1 2
2 4
3 4样例1
3
2
样例2
2
1
2
对于30%的数据，n,m≤10^3。
另有 20%20% 的数据，ai≤2。
对于 100%100% 的数据，1≤n,m≤10^5,1≤ai≤50。