{"raw_statement":[{"iden":"problem statement","content":"You are given a permutation $A = (A_1, A_2, \\dots, A_N)$ of $(1, 2, \\dots, N)$.\nFor a pair of integers $l, r$ ($1 \\le l \\le r \\le N$), we define the **Cartesian Tree** $\\text{C}(l, r)$ as follows:\n\n*   $\\text{C}(l, r)$ is a rooted binary tree with $r - l + 1$ nodes. We denote the root of this tree as $\\mathit{rt}$.\n*   Let $m$ be the unique integer such that $A_m = \\min\\lbrace A_l, A_{l+1}, \\dots, A_r\\rbrace$.\n*   If $l < m$, then the left subtree of $\\mathit{rt}$ is $\\text{C}(l, m-1)$. If $l = m$, then $\\mathit{rt}$ has no left child.\n*   If $m < r$, then the right subtree of $\\mathit{rt}$ is $\\text{C}(m+1, r)$. If $m = r$, then $\\mathit{rt}$ has no right child.\n\nYou are given $Q$ pairs of integers $(l_1, r_1), (l_2, r_2), \\dots, (l_Q, r_Q)$. Determine how many different Cartesian Trees are there among $\\text{C}(l_1, r_1), \\text{C}(l_2, r_2), \\dots, \\text{C}(l_Q, r_Q)$.\nTwo Cartesian Trees $X$ and $Y$ are considered the same if and only if all of the following conditions are satisfied:\n\n> Let the root of $X$ be $\\mathit{rt}_X$, and the root of $Y$ be $\\mathit{rt}_Y$.\n> \n> *   If $\\mathit{rt}_X$ has a left child, then $\\mathit{rt}_Y$ also has a left child and the left subtrees of $\\mathit{rt}_X$ and $\\mathit{rt}_Y$ are the same Cartesian Tree.\n> *   If $\\mathit{rt}_X$ has no left child, then $\\mathit{rt}_Y$ also has no left child.\n> *   If $\\mathit{rt}_X$ has a right child, then $\\mathit{rt}_Y$ also has a right child and the right subtrees of $\\mathit{rt}_X$ and $\\mathit{rt}_Y$ are the same Cartesian Tree.\n> *   If $\\mathit{rt}_X$ has no right child, then $\\mathit{rt}_Y$ also has no right child."},{"iden":"constraints","content":"*   All input values are integers.\n*   $1 \\le N \\le 4 \\times 10^5$\n*   $A$ is a permutation of $(1, 2, \\dots, N)$.\n*   $1 \\le Q \\le 4 \\times 10^5$\n*   $1 \\le l_i \\le r_i \\le N$ ($1 \\le i \\le Q$)\n*   $(l_i, r_i) \\ne (l_j, r_j)$ ($1 \\le i < j \\le Q$)"},{"iden":"input","content":"The input is given in the following format:\n\n$N$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n$Q$\n$l_1$ $r_1$\n$l_2$ $r_2$\n$\\vdots$\n$l_Q$ $r_Q$"},{"iden":"sample input 1","content":"6\n1 4 2 6 3 5\n3\n1 4\n2 5\n3 6"},{"iden":"sample output 1","content":"2\n\n$\\text{C}(1, 4), \\text{C}(2, 5), \\text{C}(3, 6)$ are the following Cartesian Trees:\n![image](https://img.atcoder.jp/ttpc2024_1/db8d0d930aa8deab6edbf6d1cc510f0f.svg)\n$\\text{C}(1, 4)$ and $\\text{C}(3, 6)$ are the same Cartesian Tree, while $\\text{C}(2, 5)$ is a different Cartesian Tree from these. Therefore, there are $2$ different Cartesian Trees."},{"iden":"sample input 2","content":"4\n1 2 3 4\n10\n1 1\n2 2\n3 3\n4 4\n1 2\n2 3\n3 4\n1 3\n2 4\n1 4"},{"iden":"sample output 2","content":"4"},{"iden":"sample input 3","content":"10\n3 8 4 7 2 5 9 10 1 6\n13\n5 8\n2 6\n7 9\n3 8\n3 5\n2 4\n4 6\n1 9\n3 7\n6 9\n2 10\n4 9\n3 9"},{"iden":"sample output 3","content":"11"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}