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\)