You have been given a sequence A of N digits. Each digit in this sequence ranges from 1 to $10^9$ . You need to perform 2 types of operations on this list:

• $Add(x)$: Add element x to the end of the list.
• $Max(list)$: Find the maximum element in the current sequence.

For each query of type 2, you need to print the result of that operation.

Input Format

The first line consist of a single integer N denoting the size of the initial sequence. The next line consists of N space separated integers denoting the elements of the initial sequence. The next line contains a single integer q denoting the number of queries. The next q lines contains the details of the operation. The first integer type indicates the type of query. If type_i ==1, it is followed by another integer x and you need to perform operation of type 1 else operations of type 2

Output Format

For each operation of the second type, print a single integer on a new line.

Constraints

$1 \le N \le 10^5$

$1 \le a[i] \le 10^9$

$1 \le q \le 10^4$