← 返回题目列表

Codeforces · 997/E

E. 好的细分

中文机器翻译题面 查看原题

长度为 $$$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