NEKAMELEONI - NEKAMELEONI

"Hey! I have an awesome task with chameleons, 5th task for Saturday’s competition."

"Go ahead..."

(...)

“That’s too difficult, I have an easier one, they won’t even solve that one.”

“You are given an array of N integers from the interval [1, K]. You need to process M queries. The first type of query requires you to change a number in the array to a different value, and the second type of query requires you to determine the length of the shortest contiguous subarray of the current array that contains all numbers from 1 to K.”

“Hm, I can do it in O(N6). What’s the limit for N?”

Input

The first line of input contains the integers N, K and M (1 <= N, M <= 100 000, 1 <= K <= 50). The second line of input contains N integers separated by space, the integers from the array. After that, M queries follow, each in one of the following two forms:

  • “1 p v” - change the value of the pth number into v (1 <= p <= N, 1 <= v <= K)
  • “2” - what is the length of the shortest contiguous subarray of the array containing all the integers from 1 to K

Output

The output must consist of the answers to the queries of the second type, each in its own line.

If the required subarray doesn’t exist, output −1.

Example

Input:
4 3 5
2 3 1 2
2
1 3 3
2
1 1 1
2

Output:
3
-1
4

Added by:Gầy :))
Date:2015-11-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:COCI 2015 Round 3

hide comments
2015-12-18 22:05:54 abdou_93
only one second!!
TEL with O(N*K log N) + O(M*K log N),
any help
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.