9037: Jujubesister

内存限制:1024 MB 时间限制:6 S
题面:传统 评测方式:文本比较 上传者:
提交:2 通过:0

题目描述

Follow zaozijie Meow, follow zaozijie Thank you Meow.

Given a sequence of integers a1,…,ana_1,\dots,a_na1,,an , you need to answer mmm questions.
The answer to a question l,rl,rl,r is the amount of (i,j,k)(i,j,k)(i,j,k) s.t. l≤i<j<k≤r,ai=ak>ajl\le i<j<k\le r,\;a_i=a_k>a_jli<j<kr,ai=ak>aj .

1ain
1≤l≤r≤n1\le l\le r\le n1lrn
1≤n,m≤5×1051\le n,m\le 5\times 10^51n,m5×105

输入格式

The first line contains two integers n,mn,mn,m .
The next line contains nnn integers a1,…,ana_1,\dots,a_na1,,an.
For the next mmm lines, each line contains two integers l,rl,rl,r , means a question.

输出格式

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

输入样例 复制

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

输出样例 复制

4
4
1
0
0