Maximum Absolute Value in Subarrays

You are given an array of n integers and q queries. Each query contains two integers l and r (1-indexed), representing the subarray from index l to index r inclusive. For each query, your task is to find the maximum absolute value of the numbers within the specified subarray. In other words, for a given subarray, compute:

[ \max_{l \leq i \leq r} \left|a_i\right| ]

where \(a_i\) represents the elements of the array. Output the result for each query on a new line.

inputFormat

The first line contains an integer n (the number of elements in the array).

The second line contains n space-separated integers representing the array.

The third line contains an integer q (the number of queries).

The following q lines each contain two integers l and r denoting the starting and ending indices (inclusive) of the subarray.

outputFormat

For each query, output a single line containing the maximum absolute value found in the corresponding subarray.

## sample

8
-3 7 -2 10 -5 7 3 -4
3
1 4
2 6
3 8

10
10
10

</p>