D. Depth of Cartesian Tree
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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.
Input

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$$$.

Output

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

Example
Input
7 10
1 5 4 7 2 6 3
1 7
1 3
2 4
3 5
4 6
5 7
1 4
2 5
3 6
4 7
Output
10
2
3
2
3
2
5
4
4
5