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 must not solve that query.

Input format

• First line: An integer $N$ as input that denotes the total number of elements of the array
• Next line: $N$ space-separated integers that denote the elements of that array
• Next line: An integer $Q$ that denotes the total number of queries
• Next $Q$ lines: Description of each query that begins with an integer $type$ that is $1$ for the first type of queries and $2$ for the second type of queries

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

Constraints

Subtask 1: 50 marks

$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 marks

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

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

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

$1 \le X , Y \le N$