QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 512 MB
[0]
Statistics

题目描述

给定一个长为 n 的序列 a

m 次询问,每次询问给定一个区间 [l,r],求 |{(ai,aj):li<jrai>aj}|

1n1051m5×105

输入格式

第一行一个正整数 n

第二行 n 个正整数,其中第 i 个数 ai 表示序列第 i 个位置的值,保证 1ain

第三行一个正整数 m

之后 m 行,每行用两个空格隔开的正整数,分别表示 l,r,表示一次询问,保证 1lrn

输出格式

输出 m 行,第 i 行输出一行一个整数,表示第 i 次询问的答案。

样例数据

样例 1 输入

5
2 1 3 2 1
4
2 4
1 5
3 5
2 2

样例 1 输出

1
3
3
0

样例 1 解释

对于第一次询问,集合为 {(3,1)}

对于第二次与第三次询问,集合为 {(2,1),(3,1),(3,2)}

对于第四次询问,集合为空集。