逆序对计数
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

大小为 的排列是大小为 的数组且使得从 到 的每个整数在该数组中恰好出现一次。对于给定的一个排列，逆序对就是排列中  且 的有序对。例如，一个排列  包含 4 个逆序对,  , , (3, 2) , (4, 2) 。
您将获得一个大小为 的排列 并对其进行 次询问。每个询问由两个索引 和 表示，表示您必须反转排列的段  。例如，如果  和查询  ,  ，那么得到的排列是  。每次询问后，您需要输出逆序对的数量。每次询问相互独立，即该次查询询问对下一次询问不产生影响。

输入描述:

第一行包含一个整数   ,表示排列的大小。
第二行包含  个整数 a_1, a_2, ..., a_n  ,排列的元素,这些整数是成对不同的。
第三行包含一个整数   ,要处理的询问数。
接下来  行，接下来的第  行包含两个整数l_i , r_i  表示第   个查询是反转排列的段 l_i , r_i 。

输出描述:

 行,每行一个整数代表询问的结果。
示例1

输入

复制 
5
5 3 1 2 4
4
2 3
1 4
1 5
3 4

输出

复制 
5
2
4
7

说明

所有询问独立,对于该样例,
询问区间  时,排列变成 5 , 1 , 3 , 2 , 4 , 有逆序对 , (5,1) , (5,2) , (5,3) , (5,4) , (3,2) 。
询问区间  时,排列变成 4 , 2 , 1 , 3 , 5 , 有逆序对 , (4,2) , (4,3) , (4,1) , (2,1) 。