题目描述

给出一组整数，它的前 x 个数称为它的前缀，前缀最值差指的是：数组前 x 个数中最大值 和最小值的差，这个问题到也难不倒小明。 但现在有 q 个问题询问，要求算出每个问题的前缀最值差。这样工作量就太大了。你有 什么办法吗？

输入格式

第一行有一个正整数 N，表示给出的这组正整数的个数。 第二行有 N 个正整数 ai 。 第三行有一个正整数 q,表示有 q 个询问。 第四行有 q 个正整数 xi，分别表示要求前 xi 个数中最大值和最小值的差。

输出格式

输出，每个询问的答案。

6
1 3 1 7 2 4
3
3 2 6

2 2 6

数据规模与约定

50%数据, 1<= N<=1000, q<=1000, ai<1000,1<=xi<=N; 100%数据, 1<= N<=1000000, q<=1000000, ai<1000000000,1<=xi<=N;