#P3289. Mato的文件管理

    ID: 2476 传统题 1000ms 512MiB 尝试: 5262 已通过: 1310 难度: 6 上传者: 标签>难度分类提高离线与分治普通莫队数据结构树状数组排序与序列处理离散化奇偶块排序CF1900Bytaorunz

Mato的文件管理

题目描述

Mato 从各路高手那里用各种方式收集了 nn 份资料。每份资料都有大小和编号。资料经过加密,只能用 Mato 自己编写的程序访问。

Mato 每天选择一个区间 [l,r][l,r],阅读该区间内的资料。他习惯按文件大小从小到大阅读。每天他先按编号顺序复制这批文件,再用程序对文件排序。由于加密,程序无法随机访问,每单位时间只能交换两个相邻文件。

对每一天,求把复制出来的文件按大小排成非递减顺序所需的最少相邻交换次数。

输入格式

从标准输入读入。第一行是正整数 nn。第二行有 nn 个正整数,第 ii 个是编号为 ii 的文件的大小。第三行是正整数 qq,表示天数。之后 qq 行各有两个正整数 l,rl,r,表示当天的文件区间。

输出格式

向标准输出写入。输出 qq 行,每行一个整数,表示对应区间所需的最少交换次数。

样例 1

4
1 4 2 3
2
1 2
2 4
0
2

样例解释

第一天无需交换。第二天可将编号为 22 的文件向后交换两次,把它移动到最后。

数据范围

1≤n,q≤500001\le n,q\le 50000,1≤l≤r≤n1\le l\le r\le n。