Jujubesister

题号：NC256176
时间限制：C/C++/Rust/Pascal 6秒，其他语言12秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

Follow zaozijie Meow, follow zaozijie Thank you Meow.

Given a sequence of integers $a_1,\dots,a_n$ , you need to answer $m$ questions.

The answer to a question $l,r$ is the amount of $(i,j,k)$ s.t. $l\le i<j<k\le r,\;a_i=a_k>a_j$ .

$1\le a_i\le n$
$1\le l\le r\le n$
$1\le n,m\le 5\times 10^5$

The first line contains two integers  .
The next line contains  integers .
For the next  lines, each line contains two integers  , means a question.

For each question, output a line containing a single integer representing the answer.

示例1

复制

10 5
9 8 5 4 5 1 5 1 5 8
2 8
4 9
7 9
6 7
2 3

复制