当前没有测试数据。

题目描述

给你一个长度为 $n$ 的数组，有 $q$ 组询问，每次询问一个区间内所有数字的极差 $（max-min）$。

输入格式

第一行，一个正整数 $n$，表示数组长度。

第二行，$n$ 个正整数 $a[i]$，表示给定数组。

第三行，一个正整数 $q$，表示询问数。

接下来 $q$ 行，每行两个正整数 $l,r$，表示询问的区间。

输出格式

对于每个询问输出一行，表示答案。

样例

10
22 14 7 9 16 10 13 21 16 18
6
2 4
3 7
6 9
4 8
7 10
1 5

7
9
11
12
8
15

数据范围

对于 $40\%$ 的数据，$2 \le n \le 5000, 1 \le q \le 5000$。

对于 $100\%$ 的数据，$2 \le n \le 10^5, 1 \le q \le 10^6, 1 \le a[i] \le 10^9, 1 \le l$