You are given an array $A$ of $N$ elements. Each element belongs to its own group initially.

You need to process the following two types of queries:

$1$  $X$  $Y$ - The array elements which are  at positions  $X$ and $Y$ in the array  $A$  merge their group.
$2$  $X$ - Print the maximum absolute difference of the array values that belong to the group of $X^{th}$ element of the array.

Note: It is possible that the elements $X$ and $Y$ in the query of type $1$ already be in the same group. You need to simply ignore that query.

Input
The first line contains an integer $N$ as input that denotes the total number of elements of the array. The next line contains $N$ space separated integers that denote the elements of that array.
The next line of input contains an integer $Q$ that denotes the total number of queries. 
The next $Q$ lines contain description of each query.
The description of each query begins with an integer $type$ which is 1 for 1st type of queries and 2 for second type of queries.

Output
For each query of type $2$, print the answer in a new line.

Constraints:

Subtask 1: 50 Points

$1 \le N \le 10^{3}$

$|A[i]| \le 10^{3}$

$1 \le Q \le 10^{3}$

$1 \le X , Y \le N$

Subtask 2: 50 Points

$1 \le N \le 10^{6}$

$|A[i]| \le 10^{9}$

$1 \le Q \le 5*10^{5}$

$1 \le X , Y \le N$