English · Original
Chinese · Translation
Formal · Original
A permutation $p$ of length $n$ is a sequence $p_1, p_2, \ldots, p_n$ consisting of $n$ distinct integers, each of which from $1$ to $n$ ($1 \leq p_i \leq n$) .
Let's call the subsegment $[l,r]$ of the permutation **good** if all numbers from the minimum on it to the maximum on this subsegment occur among the numbers $p_l, p_{l+1}, \dots, p_r$.
For example, good segments of permutation $[1, 3, 2, 5, 4]$ are:
* $[1, 1]$,
* $[1, 3]$,
* $[1, 5]$,
* $[2, 2]$,
* $[2, 3]$,
* $[2, 5]$,
* $[3, 3]$,
* $[4, 4]$,
* $[4, 5]$,
* $[5, 5]$.
You are given a permutation $p_1, p_2, \ldots, p_n$.
You need to answer $q$ queries of the form: find the number of good subsegments of the given segment of permutation.
In other words, to answer one query, you need to calculate the number of good subsegments $[x \dots y]$ for some given segment $[l \dots r]$, such that $l \leq x \leq y \leq r$.
## Input
The first line contains a single integer $n$ ($1 \leq n \leq 120000$) — the number of elements in the permutation.
The second line contains $n$ distinct integers $p_1, p_2, \ldots, p_n$ separated by spaces ($1 \leq p_i \leq n$).
The third line contains an integer $q$ ($1 \leq q \leq 120000$) — number of queries.
The following $q$ lines describe queries, each line contains a pair of integers $l$, $r$ separated by space ($1 \leq l \leq r \leq n$).
## Output
Print a $q$ lines, $i$\-th of them should contain a number of good subsegments of a segment, given in the $i$\-th query.
[samples]
长度为 $n$ 的排列 $p$ 是由 $n$ 个互不相同的整数组成的序列 $p_1, p_2, dots.h, p_n$，其中每个整数都在 $1$ 到 $n$ 之间（$1 lt.eq p_i lt.eq n$）。
我们称排列的子段 $[ l, r ]$ 为 *好* 的，如果从该子段的最小值到最大值之间的所有整数都出现在 $p_l, p_(l + 1), dots.h, p_r$ 中。
例如，排列 $[ 1, 3, 2, 5, 4 ]$ 的好子段有：
给定一个排列 $p_1, p_2, dots.h, p_n$。
你需要回答 $q$ 个查询，每个查询的形式为：求给定排列段中好子段的数量。
换句话说，对于每个查询，你需要计算在给定段 $[ l dots.h r ]$ 中，满足 $l lt.eq x lt.eq y lt.eq r$ 的好子段 $[ x dots.h y ]$ 的数量。
第一行包含一个整数 $n$（$1 lt.eq n lt.eq 120000$）——排列的元素个数。
第二行包含 $n$ 个用空格分隔的互不相同的整数 $p_1, p_2, dots.h, p_n$（$1 lt.eq p_i lt.eq n$）。
第三行包含一个整数 $q$（$1 lt.eq q lt.eq 120000$）——查询的数量。
接下来的 $q$ 行描述查询，每行包含一对用空格分隔的整数 $l$ 和 $r$（$1 lt.eq l lt.eq r lt.eq n$）。
请输出 $q$ 行，第 $i$ 行应包含第 $i$ 个查询中给定段的好子段数量。
## Input
第一行包含一个整数 $n$（$1 lt.eq n lt.eq 120000$）——排列的元素个数。第二行包含 $n$ 个用空格分隔的互不相同的整数 $p_1, p_2, dots.h, p_n$（$1 lt.eq p_i lt.eq n$）。第三行包含一个整数 $q$（$1 lt.eq q lt.eq 120000$）——查询的数量。接下来的 $q$ 行描述查询，每行包含一对用空格分隔的整数 $l$ 和 $r$（$1 lt.eq l lt.eq r lt.eq n$）。
## Output
请输出 $q$ 行，第 $i$ 行应包含第 $i$ 个查询中给定段的好子段数量。
[samples]
**Definitions**
Let $ p = (p_1, p_2, \dots, p_n) $ be a permutation of $ \{1, 2, \dots, n\} $.
A subsegment $ [x, y] $ (with $ 1 \le x \le y \le n $) is called *good* if:
$$
\{ p_x, p_{x+1}, \dots, p_y \} = \{ m, m+1, \dots, M \}
$$
where $ m = \min\{p_x, \dots, p_y\} $ and $ M = \max\{p_x, \dots, p_y\} $.
Let $ Q = \{ (l_j, r_j) \mid j \in \{1, \dots, q\} \} $ be the set of queries.
**Constraints**
1. $ 1 \le n \le 120000 $
2. $ 1 \le q \le 120000 $
3. For each query $ j $: $ 1 \le l_j \le r_j \le n $
**Objective**
For each query $ j \in \{1, \dots, q\} $, compute:
$$
\left| \left\{ [x, y] \mid l_j \le x \le y \le r_j \text{ and } [x, y] \text{ is good} \right\} \right|
$$
API Response (JSON)
{
"problem": {
"name": "E. Good Subsegments",
"description": {
"content": "A permutation $p$ of length $n$ is a sequence $p_1, p_2, \\ldots, p_n$ consisting of $n$ distinct integers, each of which from $1$ to $n$ ($1 \\leq p_i \\leq n$) . Let's call the subsegment $[l,r]$ of t",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 7000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF997E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "A permutation $p$ of length $n$ is a sequence $p_1, p_2, \\ldots, p_n$ consisting of $n$ distinct integers, each of which from $1$ to $n$ ($1 \\leq p_i \\leq n$) .\n\nLet's call the subsegment $[l,r]$ of t...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "长度为 $n$ 的排列 $p$ 是由 $n$ 个互不相同的整数组成的序列 $p_1, p_2, dots.h, p_n$，其中每个整数都在 $1$ 到 $n$ 之间（$1 lt.eq p_i lt.eq n$）。\n\n我们称排列的子段 $[ l, r ]$ 为 *好* 的，如果从该子段的最小值到最大值之间的所有整数都出现在 $p_l, p_(l + 1), dots.h, p_r$ 中。\n\n例如，排...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ p = (p_1, p_2, \\dots, p_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $. \nA subsegment $ [x, y] $ (with $ 1 \\le x \\le y \\le n $) is called *good* if: \n$$\n\\{ p_x, p_{x+1}, \\do...",
"is_translate": false,
"language": "Formal"
}
]
}