2513: 蒜头君的排序
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：7
Solved：0
Description
蒜头君是一个爱思考的好孩子，这一天他学习了冒泡排序，于是他就想，把一个乱序排列通过冒泡排序排至升序需要多少次交换，这当然难不倒他，于是他想来点刺激的，给定一个 1…n 的排列，每次从该排列中选择一个区间 [l,r]，问使用冒泡排序将该区间排至升序需要多少次交换操作。
Input
第一行一个整数 n，表示排列长度。
接下来一行 n 个整数，表示该排列。
接下来一行一个整数 m，表示询问次数。
接下来 m 行，每行 2 个整数 l,r，表示询问 [l,r] 区间。
Output
输出 m 行，每行 1 个整数，第 i 行表示第 i 个询问的答案。
Sample Input Copy
10
9 8 7 4 5 6 10 3 2 1
5
2 4
8 10
2 8
5 9
4 9Sample Output Copy
3
3
13
7
9HINT
对于 30% 的数据，满足 1≤n,m≤300；
对于 60% 的数据，满足 1≤n,m≤1000；
对于 100% 的数据，满足 1≤n,m≤30000, l<r, ∑∣l[i]−l[i−1]∣ + ∑∣r[i]−r[i−1]∣≤ 7×106。