Difference

问题描述

给定一个0到N-1共N(2<=N<=2^16)个点的区间,每个点i有一个值(0 < Vi < 10^9).
现给出Q(1<=Q<=10^6)个询问,每个询问给出两个值,a,b(0 <= a < b < N)
求[a,b]区间内最大值和第二大的值(允许和最大值相等)之差.

输入说明

最多10组Case,以EOF结束
每组数据中:
第一行:数字N 接下来一行,共N个数,表示Vi.
接下来一行,数字 Q
接下来Q行,每行两个数a和b,以空格分隔.

输出说明

每组数据先输出一行"Case %d:",%d为Case编号 接下来Q行,输出最大值减去次大值的差.

输入样例

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

输出样例

Case 1:
1
1
1
Case 2:
4
1
3