AT_ttpc2024_1_m Cartesian Trees

You are given a permutation $ A = (A_1, A_2, \dots, A_N) $ of $ (1, 2, \dots, N) $ . For a pair of integers $ l, r $ ( $ 1 \le l \le r \le N $ ), we define the **Cartesian Tree** $ \text{C}(l, r) $ as follows: - $ \text{C}(l, r) $ is a rooted binary tree with $ r - l + 1 $ nodes. We denote the root of this tree as $ \mathit{rt} $ . - Let $ m $ be the unique integer such that $ A_m = \min\lbrace A_l, A_{l+1}, \dots, A_r\rbrace $ . - 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. - 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. You 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) $ . Two Cartesian Trees $ X $ and $ Y $ are considered the same if and only if all of the following conditions are satisfied: > Let the root of $ X $ be $ \mathit{rt}_X $ , and the root of $ Y $ be $ \mathit{rt}_Y $ . > > - 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. > - If $ \mathit{rt}_X $ has no left child, then $ \mathit{rt}_Y $ also has no left child. > - 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. > - If $ \mathit{rt}_X $ has no right child, then $ \mathit{rt}_Y $ also has no right child.

The input is given in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ Q $ $ l_1 $ $ r_1 $ $ l_2 $ $ r_2 $ $ \vdots $ $ l_Q $ $ r_Q $

Print the answer.

### Sample Explanation 1 $ \text{C}(1, 4), \text{C}(2, 5), \text{C}(3, 6) $ are the following Cartesian Trees:  $ \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. ### Constraints - All input values are integers. - $ 1 \le N \le 4 \times 10^5 $ - $ A $ is a permutation of $ (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 $ )