题目描述
给定一个长为 n 的序列 a。
有 m 次询问,每次询问给定一个区间 [l,r],求 |{(ai,aj):l≤i<j≤r∧ai>aj}|。
1≤n≤105,1≤m≤5×105。
输入格式
第一行一个正整数 n。
第二行 n 个正整数,其中第 i 个数 ai 表示序列第 i 个位置的值,保证 1≤ai≤n。
第三行一个正整数 m。
之后 m 行,每行用两个空格隔开的正整数,分别表示 l,r,表示一次询问,保证 1≤l≤r≤n。
输出格式
输出 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)}。
对于第四次询问,集合为空集。