Arun, Barun and Kiranmala are brothers and sisters. Arun and Barun always try to make their sister happy. They know Kiranmala will be happy if they give her a largest possible flower. Flower garden can be described as an array of integers and each value represents size of the flower. But their life is not so easy as a giant is in guard of the flower garden. However giant can protect only those flowers which are within his range, which means they cannot get those flowers. Now your job is to help Arun and  Barun finding largest possible flower they can get. You are given an array of n integers(array describing the size of the flowers), followed by q queries. Each query consists of two numbers i and j, which describes the range of the giant i and j inclusive(0 indexed).

Input

First line contains an integer n. (1 ≤ n ≤ 10000)

next line contains n integers.

next line contains q. Number of queries. (1 ≤ q ≤ 10000)

next q lines contains two elements i and j (1 ≤ i ≤ j ≤ 10000)

Output

q lines containing the output for q queries.

Example

Input:
5
2 5 1 7 9
2
2 3
1 4

Output:
9
2