题目描述
大小为 nnn 的排列是大小为 nnn 的数组且使得从 111 到 nnn 的每个整数在该数组中恰好出现一次。对于给定的一个排列，逆序对就是排列中 i>ji>ji>j 且 ai<aja_i < a_jai<aj 的有序对。例如，一个排列 [3，4，1，2][3，4，1，2][3，4，1，2] 包含 4 个逆序对, (3，1)(3，1)(3，1) , (4，1)(4，1)(4，1) , (3,2)(3, 2)(3,2) , (4,2)(4, 2)(4,2) 。
您将获得一个大小为 nnn 的排列 aaa 并对其进行 mmm 次询问。每个询问由两个索引 lll 和 rrr 表示，表示您必须反转排列的段 [l,r][l, r][l,r] 。例如，如果 a=[1,2,3,4,5]a = [1,2,3, 4,5]a=[1,2,3,4,5] 和查询 l=2l = 2l=2 , r=4r = 4r=4 ，那么得到的排列是 [1,4,3,2,5][1,4,3,2,5][1,4,3,2,5] 。每次询问后，您需要输出逆序对的数量。每次询问相互独立，即该次查询询问对下一次询问不产生影响。
您将获得一个大小为 nnn 的排列 aaa 并对其进行 mmm 次询问。每个询问由两个索引 lll 和 rrr 表示，表示您必须反转排列的段 [l,r][l, r][l,r] 。例如，如果 a=[1,2,3,4,5]a = [1,2,3, 4,5]a=[1,2,3,4,5] 和查询 l=2l = 2l=2 , r=4r = 4r=4 ，那么得到的排列是 [1,4,3,2,5][1,4,3,2,5][1,4,3,2,5] 。每次询问后，您需要输出逆序对的数量。每次询问相互独立，即该次查询询问对下一次询问不产生影响。
输入
第一行包含一个整数 nnn (1≤n≤6000)(1 ≤ n ≤ 6000)(1≤n≤6000) ,表示排列的大小。
第二行包含 nnn 个整数 a1,a2,...,ana_1, a_2, ..., a_na1,a2,...,an (1≤ai≤n)(1 ≤ a_i ≤ n)(1≤ai≤n) ,排列的元素,这些整数是成对不同的。
第二行包含 nnn 个整数 a1,a2,...,ana_1, a_2, ..., a_na1,a2,...,an (1≤ai≤n)(1 ≤ a_i ≤ n)(1≤ai≤n) ,排列的元素,这些整数是成对不同的。
第三行包含一个整数 qqq (1≤q≤2×105)(1 ≤ q ≤ 2\times10^5)(1≤q≤2×105) ,要处理的询问数。
接下来 qqq 行，接下来的第 iii 行包含两个整数lil_ili , rir_iri (1≤li≤ri≤n)(1 ≤ l_i ≤ r_i ≤ n)(1≤li≤ri≤n) 表示第 iii 个查询是反转排列的段 lil_ili , rir_iri 。
输出
q 行,每行一个整数代表询问的结果。 样例输入 Copy
5
5 3 1 2 4
4
2 3
1 4
1 5
3 4
样例输出 Copy
5
2
4
7
提示
所有询问独立,对于该样例,
询问区间 [2,3][2,3][2,3] 时,排列变成 555 , 111 , 333 , 222 , 444 , 有逆序对 , (5,1)(5,1)(5,1) , (5,2)(5,2)(5,2) , (5,3)(5,3)(5,3) , (5,4)(5,4)(5,4) , (3,2)(3,2)(3,2) 。
询问区间 [1,5][1,5][1,5] 时,排列变成 444 , 222 , 111 , 333 , 555 , 有逆序对 , (4,2)(4,2)(4,2) , (4,3)(4,3)(4,3) , (4,1)(4,1)(4,1) , (2,1)(2,1)(2,1) 。