33744번 - Depth of Cartesian Tree 다국어

문제

The cartesian tree of a sequence of distinct integers, is an unique binary tree defined as follows.

• The cartesian tree of a sequence with one element is the tree of one node;
• The root of the cartesian tree of a sequence corresponds to the maximum value of the sequence;
• If the root does not correspond to the leftmost index, the left subtree is the cartesian tree of the subarray left to it;
• If the root does not correspond to the rightmost index, the right subtree is the cartesian tree of the subarray right to it.

In a binary tree, the depth of a node is defined as the distance from the root to the node.

You are given a permutation $p$ of elements 1,2,ドル\cdots,n$. You must solve $q$ queries of the following kind.

• $l$ $r$: Assume that you construct a cartesian tree of the subsequence $p_l,p_{l+1},\cdots,p_r$. Answer the sum of the depths of all nodes in the tree.

입력

The first line contains two integers $n$ and $q$ (1ドル \leq n, q \leq 10^6$) --- the length of the permutation and number of queries respectively.

The second line contains $n$ distinct integers $p_1, p_2, \cdots, p_n$ (1ドル \leq p_i \leq n$) --- the permutation $p$.

The next $q$ lines contain two integers $l_i, r_i$ (1ドル \leq l_i \leq r_i \leq n$) --- the bounds of query $i$.

출력

For each query, output the answer on a new line.

제한

힌트