AT_1_ttpc2024_1_m.Cartesian Trees

给定一个排列 $A = (A_1, A_2, \dots, A_N)$，其为 $1$ 到 $N$ 的数字重新排序所得。对于每个区间 $(l, r)$（满足 $1 \le l \le r \le N$），我们定义一种叫做 Cartesian Tree 的结构 $\text{C}(l, r)$，定义如下：

• $\text{C}(l, r)$ 是一个有根二叉树，包含 $r - l + 1$ 个节点。树的根节点记为 $\mathit{rt}$。
• 整数 $m$ 是唯一能使 $A_m = \min\{A_l, A_{l+1}, \dots, A_r\}$ 成立的值。
• 若 $l < m$，则 $\mathit{rt}$ 的左子树构造为 $\text{C}(l, m-1)$；否则，$\mathit{rt}$ 没有左子树。
• 若 $m < r$，则 $\mathit{rt}$ 的右子树构造为 $\text{C}(m+1, r)$；否则，$\mathit{rt}$ 没有右子树。

现在给出 $Q$ 个区间对 $(l_1, r_1), (l_2, r_2), \dots, (l_Q, r_Q)$，需要你判断这些区间内所构造的 Cartesian Tree 中，有多少种是不一样的。具体而言，两个 Cartesian Tree 被认为是相同的，当且仅当它们的结构完全相同。即：

• 如果 $X$ 的根节点 $\mathit{rt}_X$ 有左子树，那么 $Y$ 的根节点 $\mathit{rt}_Y$ 也必须有左子树，而且 $X$ 和 $Y$ 的左子树构造的 Cartesian Tree 要完全相同。
• 如果 $X$ 的根节点 $\mathit{rt}_X$ 没有左子树，那么 $Y$ 的根节点 $\mathit{rt}_Y$ 也不能有左子树。
• 如果 $X$ 的根节点 $\mathit{rt}_X$ 有右子树，那么 $Y$ 的根节点 $\mathit{rt}_Y$ 也必须有右子树，而且 $X$ 和 $Y$ 的右子树构造的 Cartesian Tree 要完全相同。
• 如果 $X$ 的根节点 $\mathit{rt}_X$ 没有右子树，那么 $Y$ 的根节点 $\mathit{rt}_Y$ 也不能有右子树。

输入包含一行，以以下格式给出：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$ $Q$ $l_1$ $r_1$ $l_2$ $r_2$ $\vdots$ $l_Q$ $r_Q$

输出一种整数，表示不一样的 Cartesian Tree 的数量。

• 所有输入均为整数。
• $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$ 成立。
• 对任意的 $i \ne j$，$(l_i, r_i) \ne (l_j, r_j)$。

本翻译由 AI 自动生成