1041: 集训队的舞会

在神奇的NWU-ACM集训队中，有各种各样的成员。每个人都非常独特，每个人都使用一个数代表他们的特点，大家使用的数字各不相同。

最近，集训队决定选择一些人举办一场盛大的舞会，参加舞会的人希望能够找到自己的配对对象并一起参加。每个队员都会有一个配对对象，而且每对队员之间的匹配是相互的。例如，队员A的配对对象是队员B，那么队员B的配对对象就是队员A。

作为一对，我们定义两人的分歧值是这两个人所对应的数字之差的绝对值。为了让舞会完美举办，我们希望每个队伍的分歧值全部加起来最小。请你来安排如何配对，让集训队能够最大程度地享受这次舞会，你只需要输出能够得到的最小分歧值之和。

你将会得到一个数组，数组中的数字代表每个人的特点。同时，你将会回答多次查询，每次询问一个偶数长的区间，代表区间内的人将参加舞会。

输入的第一行是一个正整数$N$ $(1 \leq N \leq 2*10^4)$，表示数组长度。

第二行中有$N$个正整数，每个数$x$$(1 \leq x \leq 1*10^9)$都不相同，代表数组，用空格隔开。

第三行有一个正整数$Q$ $(1 \leq Q \leq 3*10^5)$，代表询问次数。

之后的$Q$行，每行输入 $2$ 个正整数$l$，$r$$(1 \leq l,r \leq N)$，代表所询问区间的起始点和终止点，保证区间长度是偶数。

输出一行，一行内共 $Q$ 个整数，第 $i$ 个整数代表第$i$次查询中能够得到的最小分歧值之和。

4
1 2 3 4
2
1 4
2 3

2 1