Background

“Hey, dear! I’m going to create Task 5 for the Croatian Open Competition In Informatics on $11$ November $28$.”
“Go ahead, go ahead…”
“…”

---

“How about this problem?”
“Um… this is too hard… it will stump those cuties. Make it easier…”
So the lovely problem setter made this problem.

---

Hey! I have an $O(n^6)$ solution. What is the range of $n$??

Problem Description

You are given an array with $n$ elements. You need to process $q$ queries.

• The first type of query asks you to change the $p$-th number in the array to $v$.
• The second type of query asks you to determine the length of the shortest contiguous subarray in the current array that contains all numbers from $1$ to $k$.

Input Format

The first line contains three positive integers $n, k, m$.

The second line contains $n$ positive integers separated by spaces, representing the numbers in the array.

Then follow $m$ lines describing $m$ queries. Each query has one of the following two forms.

• $\texttt{1 p v}$: change the $p$-th number in the array to $v$.
• $\texttt{2}$: determine and output the length of the shortest contiguous subarray in the current array that contains all numbers from $1$ to $k$.

Output Format

Only query $\texttt{2}$ produces output.

For each query $\texttt{2}$, output the length of the shortest contiguous subarray in the current array (which must contain all numbers from $1$ to $k$). If no such subarray exists, output $\texttt{-1}$.

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

3
-1
4

6 3 6
1 2 3 2 1 1
2
1 2 1
2
1 4 1
1 6 2
2

3
3
4

Hint

Constraints and Conventions

• For $30\%$ of the testdata, $1 \le n, m \le 5 \times 10 ^ 3$.
• For $100\%$ of the testdata, $1 \le n, m \le 10^5$, $1 \le k \le 50$, $1 \le p \le n$, $1 \le v \le k$.

Notes

Translated from COCI 2015-2016 #3 E NEKAMELEONI, full score 140.

Translated by ChatGPT 5