{"raw_statement":[{"iden":"statement","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 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$.\n\nFor example, good segments of permutation $[1, 3, 2, 5, 4]$ are:\n\n*   $[1, 1]$,\n*   $[1, 3]$,\n*   $[1, 5]$,\n*   $[2, 2]$,\n*   $[2, 3]$,\n*   $[2, 5]$,\n*   $[3, 3]$,\n*   $[4, 4]$,\n*   $[4, 5]$,\n*   $[5, 5]$.\n\nYou are given a permutation $p_1, p_2, \\ldots, p_n$.\n\nYou need to answer $q$ queries of the form: find the number of good subsegments of the given segment of permutation.\n\nIn 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$."},{"iden":"input","content":"The first line contains a single integer $n$ ($1 \\leq n \\leq 120000$) — the number of elements in the permutation.\n\nThe second line contains $n$ distinct integers $p_1, p_2, \\ldots, p_n$ separated by spaces ($1 \\leq p_i \\leq n$).\n\nThe third line contains an integer $q$ ($1 \\leq q \\leq 120000$) — number of queries.\n\nThe following $q$ lines describe queries, each line contains a pair of integers $l$, $r$ separated by space ($1 \\leq l \\leq r \\leq n$)."},{"iden":"output","content":"Print a $q$ lines, $i$\\-th of them should contain a number of good subsegments of a segment, given in the $i$\\-th query."},{"iden":"example","content":"Input\n\n5\n1 3 2 5 4\n15\n1 1\n1 2\n1 3\n1 4\n1 5\n2 2\n2 3\n2 4\n2 5\n3 3\n3 4\n3 5\n4 4\n4 5\n5 5\n\nOutput\n\n1\n2\n5\n6\n10\n1\n3\n4\n7\n1\n2\n4\n1\n3\n1"}],"translated_statement":[{"iden":"statement","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例如，排列 $[ 1, 3, 2, 5, 4 ]$ 的好子段有：\n\n给定一个排列 $p_1, p_2, dots.h, p_n$。\n\n你需要回答 $q$ 个查询，每个查询的形式为：求给定排列段中好子段的数量。\n\n换句话说，对于每个查询，你需要计算在给定段 $[ l dots.h r ]$ 中，满足 $l lt.eq x lt.eq y lt.eq r$ 的好子段 $[ x dots.h y ]$ 的数量。\n\n第一行包含一个整数 $n$（$1 lt.eq n lt.eq 120000$）——排列的元素个数。\n\n第二行包含 $n$ 个用空格分隔的互不相同的整数 $p_1, p_2, dots.h, p_n$（$1 lt.eq p_i lt.eq n$）。\n\n第三行包含一个整数 $q$（$1 lt.eq q lt.eq 120000$）——查询的数量。\n\n接下来的 $q$ 行描述查询，每行包含一对用空格分隔的整数 $l$ 和 $r$（$1 lt.eq l lt.eq r lt.eq n$）。\n\n请输出 $q$ 行，第 $i$ 行应包含第 $i$ 个查询中给定段的好子段数量。"},{"iden":"input","content":"第一行包含一个整数 $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$）。"},{"iden":"output","content":"请输出 $q$ 行，第 $i$ 行应包含第 $i$ 个查询中给定段的好子段数量。"}],"sample_group":[],"show_order":[],"formal_statement":"**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}, \\dots, p_y \\} = \\{ m, m+1, \\dots, M \\}\n$$\nwhere $ m = \\min\\{p_x, \\dots, p_y\\} $ and $ M = \\max\\{p_x, \\dots, p_y\\} $.\n\nLet $ Q = \\{ (l_j, r_j) \\mid j \\in \\{1, \\dots, q\\} \\} $ be the set of queries.\n\n**Constraints**  \n1. $ 1 \\le n \\le 120000 $  \n2. $ 1 \\le q \\le 120000 $  \n3. For each query $ j $: $ 1 \\le l_j \\le r_j \\le n $\n\n**Objective**  \nFor each query $ j \\in \\{1, \\dots, q\\} $, compute:  \n$$\n\\left| \\left\\{ [x, y] \\mid l_j \\le x \\le y \\le r_j \\text{ and } [x, y] \\text{ is good} \\right\\} \\right|\n$$","simple_statement":null,"has_page_source":false}