暂无测试数据。

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

输入格式

第一行一个整数 $n$，表示排列长度。

接下来一行 $n$ 个整数，表示该排列。

接下来一行一个整数 $m$，表示询问次数。

接下来 $m$ 行，每行 $2$ 个整数 $l,r$，表示询问 $[l,r]$ 区间。

输出格式

输出 $m$ 行，每行 $1$ 个整数，第 $i$ 行表示第 $i$ 个询问的答案。

数据规模

对于 $30$% 的数据，满足 $1 \le n,m \le 300$；

对于 $60$% 的数据，满足 $1 \le n,m \le 1000$；

对于 $100$% 的数据，满足 $1 \le n,m \le 30000,$ $l<r,$ $\sum | l[i]-l[i-1] |\ +$ $\sum | r[i]-r[i-1] | \le$ $7 \times 10^6 $。

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

3
3
13
7
9