题目描述

在电脑游戏「超级跳跃」中，主角需要在一列山峰之间跳跃，目标是到达插着旗帜的终点。

山脉由 $n$ 个连续的尖峰组成，第 $i$ 个尖峰位于横坐标 $i$，高度为 $h_i$。对于任意 $i<j$，主角可以从第 $i$ 个尖峰沿直线跳到第 $j$ 个尖峰，前提是在飞行过程中不会被其他尖峰挡住。

更形式化地说，不存在 $k$ 满足 $i<k<j$，且第 $k$ 个尖峰的顶点 $(k,h_k)$ 严格位于连接 $(i,h_i)$ 与 $(j,h_j)$ 的线段上方。

公司「打败 AI」正在训练一个控制主角的神经网络。为了生成训练数据，需要回答若干询问：给定一对下标 $l,r$，求主角从第 $l$ 个尖峰出发，到达第 $r$ 个尖峰所需的最少跳跃次数。

输入格式

第一行输入一个整数 $n$，表示尖峰数量。

第二行输入 $n$ 个整数 $h_1,h_2,\ldots,h_n$，表示各尖峰高度。

第三行输入一个整数 $q$，表示询问数量。

接下来 $q$ 行，每行输入两个整数 $l_i,r_i$，表示一次询问。

输出格式

对于每个询问，输出一个非负整数，表示最少需要的跳跃次数。

数据范围

样例

输入

8
5 3 4 3 6 2 1 4
3
1 8
2 7
4 4

输出

2
2
0

样例解释

考虑第二个询问，从第 $2$ 个尖峰到第 $7$ 个尖峰，可以选择路径：

因此需要 $2$ 次跳跃。

红色折线从高度为 $3$ 的第 $2$ 个山峰跳到高度为 $6$ 的第 $5$ 个山峰，再跳到高度为 $1$ 的第 $7$ 个山峰。

子任务