长度为 $$$n$$$ 的排列 $$$p$$$ 是一个序列 $$$p_1, p_2, \ldots, p_n$$$,由 $$$n$$$ 个不同的整数组成,每个整数从 $$$1$$$ 到 $$$n$$$ ($$$1 \leq p_i \leq n$$$) 。
如果从最小值到最大值的所有数字都出现在数字 $$$p_l, p_{l+1}, \dots, p_r$$$ 之间,则我们称排列的子分段 $$$[l,r]$$$ 为好。
例如,排列 $$$[1, 3, 2, 5, 4]$$$ 的良好分段是:
- $$$[1, 1]$$$,
- $$$[1, 3]$$$,
- $$$[1, 5]$$$,
- $$$[2, 2]$$$,
- $$$[2, 3]$$$,
- $$$[2, 5]$$$,
- $$$[3, 3]$$$,
- $$$[4, 4]$$$,
- $$$[4, 5]$$$,
- $$$[5, 5]$$$.
给你一个排列 $$$p_1, p_2, \ldots, p_n$$$。
您需要回答以下形式的 $$$q$$$ 查询:找到给定排列段的好子段的数量。
换句话说,要回答一个查询,您需要计算某个给定段 $$$[l \dots r]$$$ 的好子段的数量 $$$[x \dots y]$$$,使得 $$$l \leq x \leq y \leq r$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 120000$$$) — 排列中的元素数量。
第二行包含 $$$n$$$ 不同的整数 $$$p_1, p_2, \ldots, p_n$$$ 以空格分隔 ($$$1 \leq p_i \leq n$$$)。
第三行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 120000$$$) — 查询数。
下面的 $$$q$$$ 行描述查询,每行包含一对整数 $$$l$$$, $$$r$$$ 以空格分隔 ($$$1 \leq l \leq r \leq n$$$)。
输出
打印 $$$q$$$ 行,其中第 $$$i$$$ 行应包含第 $$$i$$$ 查询中给出的段的许多良好子段。
示例
输入 #1
5 1 3 2 5 4 15 1 1 1 2 1 3 1 4 1 5 2 2 2 3 2 4 2 5 3 3 3 4 3 5 4 4 4 5 5 5
输出 #1
1 2 5 6 10 1 3 4 7 1 2 4 1 3 1