分数: 100 点
问题陈述
给你一个排列 A = (A_1, A_2, \dots, A_N) of (1, 2, \dots, N).
对于一对整数 l, r (1 \le l \le r \le N),我们定义 笛卡尔树 $$$a$$$ 的 \text{C}(l, r) 如下:
- \text{C}(l, r) 是一个有根二叉树 r - l + 1 节点。我们将这棵树的根表示为 \mathit{rt}.
- 让 m 是唯一整数,使得 A_m = \min\lbrace A_l, A_{l+1}, \dots, A_r\rbrace.
- If l < m,则左子树 \mathit{rt} is \text{C}(l, m-1)。如果 l = m,那么 \mathit{rt} 没有左孩子。
- If m < r,则右子树 \mathit{rt} is \text{C}(m+1, r)。如果 m = r,那么 \mathit{rt} 没有右孩子。
你被给予 Q 整数对 给出了 (l_1, r_1), (l_2, r_2), \dots, (l_Q, r_Q)。确定其中有多少种不同的笛卡尔树 \text{C}(l_1, r_1), \text{C}(l_2, r_2), \dots, \text{C}(l_Q, r_Q).
两棵笛卡尔树 当且仅当满足以下所有条件时, X 和 Y 才被视为相同:
让根 X be \mathit{rt}_X,以及根 Y be \mathit{rt}_Y.
- If \mathit{rt}_X 有一个左孩子,那么 \mathit{rt}_Y 也有一个左孩子和左子树 \mathit{rt}_X 和 \mathit{rt}_Y 是相同的笛卡尔树。
- If \mathit{rt}_X 没有左孩子,那么 \mathit{rt}_Y 也没有左孩子。
- If \mathit{rt}_X 有一个右孩子,那么 \mathit{rt}_Y 也有一个右孩子和右子树 \mathit{rt}_X 和 \mathit{rt}_Y 是相同的笛卡尔树。
- If \mathit{rt}_X 没有右孩子,那么 \mathit{rt}_Y 也没有右孩子。
约束
- 所有输入值均为整数。
- 1 \le N \le 4 \times 10^5
- A 是一个排列 (1, 2, \dots, N).
- 1 \le Q \le 4 \times 10^5
- 1 \le l_i \le r_i \le N (1 \le i \le Q)
- (l_i, r_i) \ne (l_j, r_j) (1 \le i < j \le Q)
输入
输入按以下格式给出:
N A_1 A_2 \ldots A_N Q l_1 r_1 l_2 r_2 \vdots l_Q r_Q
输出
打印答案。
示例输入 1
6 1 4 2 6 3 5 3 1 4 2 5 3 6
示例输出 1
2
\text{C}(1, 4), \text{C}(2, 5), \text{C}(3, 6) 是以下笛卡尔树:
\text{C}(1, 4) 和 \text{C}(3, 6) 是相同的笛卡尔树,而 \text{C}(2, 5) 是与这些不同的笛卡尔树。因此,有 2 不同的笛卡尔树。
示例输入 2
4 1 2 3 4 10 1 1 2 2 3 3 4 4 1 2 2 3 3 4 1 3 2 4 1 4
示例输出 2
4
示例输入 3
10 3 8 4 7 2 5 9 10 1 6 13 5 8 2 6 7 9 3 8 3 5 2 4 4 6 1 9 3 7 6 9 2 10 4 9 3 9
示例输出 3
11