Minimize Distance Queries in a Sequence

You are given a sequence \(a\) of length \(n\). You need to perform \(m\) operations on this sequence. The operations are of two types:

• Type 1: Change all occurrences of a value \(x\) in the sequence to \(y\). In other words, for every \(i\) such that \(a_i = x\), set \(a_i = y\).
• Type 2: Query the sequence: find an index \(i\) such that \(a_i=x\) and an index \(j\) such that \(a_j=y\) so that the distance \(|i-j|\) is minimized, and output \(|i-j|\). If either \(x\) or \(y\) does not exist in the sequence during the query, output \(-1\).

The operations are given in order and the sequence is updated accordingly.

Note: All formulas are in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \leq n, m \leq 10^5)\) — the length of the sequence and the number of operations.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the sequence.

Each of the next \(m\) lines contains an operation in one of the following formats:

• 1 x y: Replace all occurrences of \(x\) with \(y\) in the sequence.
• 2 x y: Query the sequence for the minimum \(|i-j|\) such that \(a_i=x\) and \(a_j=y\).

If in a query operation either \(x\) or \(y\) is not found in the sequence, output \(-1\) for that query.

outputFormat

For each query operation (type 2), output a single line containing the minimum absolute difference \(|i-j|\) between an occurrence of \(x\) and an occurrence of \(y\) in the current sequence, or \(-1\) if one of the values does not exist.

sample

5 3
1 2 3 2 1
2 1 2
1 2 1
2 1 3

1
1