2513: 蒜头君的排序

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:7 Solved:0

Description

蒜头君是一个爱思考的好孩子,这一天他学习了冒泡排序,于是他就想,把一个乱序排列通过冒泡排序排至升序需要多少次交换,这当然难不倒他,于是他想来点刺激的,给定一个 1n1 \ldots n1n 的排列,每次从该排列中选择一个区间 [l,r][l,r][l,r],问使用冒泡排序将该区间排至升序需要多少次交换操作。

Input

第一行一个整数 nnn,表示排列长度。

接下来一行 nnn 个整数,表示该排列。

接下来一行一个整数 mmm,表示询问次数。

接下来 mmm 行,每行 222 个整数 l,rl,rl,r,表示询问 [l,r][l,r][l,r] 区间。

Output

输出 mmm 行,每行 111 个整数,第 iii 行表示第 iii 个询问的答案。

Sample Input Copy

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

Sample Output Copy

3
3
13
7
9

HINT

对于 303030% 的数据,满足 1n,m3001 \le n,m \le 3001n,m300

对于 606060% 的数据,满足 1n,m10001 \le n,m \le 10001n,m1000

对于 100100100% 的数据,满足 1n,m30000,1 \le n,m \le 30000,1n,m30000, l<r,l<r,l<r, l[i]l[i1] +\sum | l[i]-l[i-1] |\ +l[i]l[i1] + r[i]r[i1]\sum | r[i]-r[i-1] | \ler[i]r[i1] 7×1067 \times 10^6 7×106

加入题单

上一题 下一题 算法标签: