该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长度为 n 的数组 a，青蛙从起点 s 出发，每次跳跃遵循以下规则：

1. 跳跃条件：青蛙从位置 i 跳跃到位置 e（满足 i ≤ e < n），且区间 [i, e] 的最大值不超过 a[i]。
2. 跳跃策略：青蛙总是尽可能跳到最远的位置。

你需要处理 q 次查询，每次查询给出起点 s 和终点 t，要求计算青蛙从 s 到 t 的最少跳跃次数。若无法到达，输出 -1。

输入格式

• 第一行两个整数 n 和 q（1 ≤ n, q ≤ 1e5）。
• 第二行 n 个整数 a[0], a[1], ..., a[n-1]（1 ≤ a[i] ≤ 1e9）。
• 接下来 q 行，每行两个整数 s 和 t（0 ≤ s ≤ t ≤ n-1）。

输出格式

对于每个查询，输出最少跳跃次数，若无法到达则输出 -1。

样例输入

5 3
5 3 4 2 4
0 4
1 3
2 2

样例输出

1
2
0