Description

有n(1<=n<=100000)个数a1,a2,a3,…,an-1,an（-100000<=ai<=100000）, 对于m次（1<=m<=100000）as到at区间的询问，求该区间的任意两个数差值的最大值。

Input

输入由多组数据组成。每组数据，第1行输入一个数n；第2行输入n个整数，每个数后用空格隔开，分别表示a1,a2,……,an-1,an；第3行输入一个m。第4到m+3行，每行输入两个整数s和t(1<=s<=t<=n),表示要查询的区间为as到at。

Output

对于每个查询输出一行，表示该区间内任意两个数差值的最大值。

Sample Input

5
10 3 -2 5 -9
3
1 5
2 4
3 3
3
1 3 -5
3
1 3
2 3
1 2

Sample Output

19
7
0
8
8
2

HINT

Source