#1459. 「THUPC 2021」本质不同逆序对

「THUPC 2021」本质不同逆序对

题目描述

给定一个长为 nn 的序列 aa

mm 次询问,每次询问给定一个区间 [l,r][l,r],求 (ai,aj):li<jrai>aj|{(a_i,a_j) : l\le i<j\le r \wedge a_i>a_j}|

1n1051\le n\le 10^51m5×1051\le m\le 5\times 10^5

输入格式

第一行一个正整数 nn

第二行 nn 个正整数,其中第 ii 个数 aia_i 表示序列第 ii 个位置的值,保证1ain1\leq a_i \leq n

第三行一个正整数 mm

之后 mm 行,每行用两个空格隔开的正整数,分别表示 l,rl,r,表示一次询问,保证 1lrn1\leq l\le r \leq n

输出格式

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

样例

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

1
3
3
0

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

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

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