For a given array $a_1, a_2, a_3, ... , a_N$ of $N$ elements and an integer $K$, find the smallest sub-array size (smallest window length) where the elements in the sub-array contains all integers in range [$1, 2, ..., K$]. If there is no such sub-array, report 0.

Constraints

* $1 \leq N \leq 10^5$
* $1 \leq K \leq 10^5$
* $1 \leq a_i \leq 10^5$

Input

The input is given in the following format.

$N$ $K$
$a_1$ $a_2$ ... $a_N$

Output

Print the smallest sub-array size in a line.

Examples

Input

6 2
4 1 2 1 3 5


Output

2


Input

6 3
4 1 2 1 3 5


Output

3


Input

3 4
1 2 3


Output

0

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
class SegmentTree:

	def __init__(self, arr, func=min, ie=2 ** 63):
		self.h = (len(arr) - 1).bit_length()
		self.n = 2 ** self.h
		self.ie = ie
		self.func = func
		self.tree = [ie for _ in range(2 * self.n)]
		for i in range(len(arr)):
			self.tree[self.n + i] = arr[i]
		for i in range(1, self.n)[::-1]:
			self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1])

	def set(self, idx, x):
		idx += self.n
		self.tree[idx] = x
		while idx:
			idx >>= 1
			self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1])

	def query(self, lt, rt):
		lt += self.n
		rt += self.n
		vl = vr = self.ie
		while rt - lt > 0:
			if lt & 1:
				vl = self.func(vl, self.tree[lt])
				lt += 1
			if rt & 1:
				rt -= 1
				vr = self.func(self.tree[rt], vr)
			lt >>= 1
			rt >>= 1
		return self.func(vl, vr)
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
res = N + 1
st = SegmentTree([0] * K)
rt = 0
for lt in range(N):
	while rt < N and st.tree[1] == 0:
		if A[rt] <= K:
			st.set(A[rt] - 1, st.query(A[rt] - 1, A[rt]) + 1)
		rt += 1
	if st.tree[1] != 0:
		res = min(res, rt - lt)
	if A[lt] <= K:
		st.set(A[lt] - 1, st.query(A[lt] - 1, A[lt]) - 1)
print(res if res <= N else 0)


(n, k) = map(int, input().split())
aa = list(map(int, input().split()))
cnts = [0] * (k + 1)
ans = 1000000.0
existing = 0
r = 0
for l in range(n - k + 1):
	while r < n and existing < k:
		a = aa[r]
		if a <= k:
			cnts[a] += 1
			if cnts[a] == 1:
				existing += 1
		r += 1
	if k == existing:
		ans = min(ans, r - l)
	a = aa[l]
	if a <= k:
		cnts[a] -= 1
		if cnts[a] == 0:
			existing -= 1
print(ans if ans < 1000000.0 else 0)


(N, K) = map(lambda x: int(x), input().split())
a = list(map(lambda x: int(x), input().split()))
ans = N + 1
idx = 0
num = 0
values = [0] * K
for s in range(N):
	while idx < N and num < K:
		v = a[idx]
		if v <= K:
			values[v - 1] += 1
			if 1 == values[v - 1]:
				num += 1
		idx += 1
	if K == num:
		ans = min(ans, idx - s)
	v = a[s]
	if v <= K:
		values[v - 1] -= 1
		if 0 == values[v - 1]:
			num -= 1
ans = ans if ans < N + 1 else 0
print(ans)


class Window:

	def __init__(self, k):
		self.k = k
		self.data = [0] * k
		self.zeros = set(range(k))

	def add(self, i):
		if self.data[i - 1] == 0:
			self.zeros.remove(i - 1)
		self.data[i - 1] += 1

	def remove(self, i):
		if self.data[i - 1] == 1:
			self.zeros.add(i - 1)
		self.data[i - 1] -= 1

	def removable(self, i):
		return self.data[i - 1] > 1

	def open(self):
		return len(self.zeros) == 0

def run():
	(n, k) = [int(x) for x in input().split()]
	li = [int(x) for x in input().split()]
	w = Window(k)
	i = 0
	min_ = n + 1
	for (j, v) in enumerate(li):
		if v <= k:
			w.add(v)
			while True:
				if li[i] > k:
					pass
				elif w.removable(li[i]):
					w.remove(li[i])
				else:
					break
				i += 1
			if w.open():
				if min_ > j - i + 1:
					min_ = j - i + 1
	if min_ > n:
		print(0)
	else:
		print(min_)
run()


(N, K) = map(int, input().split())
(*A,) = map(int, input().split())
ans = N + 1
t = 0
u = [0] * K
c = 0
for s in range(N):
	while t < N and c < K:
		v = A[t]
		if v <= K:
			u[v - 1] += 1
			if u[v - 1] == 1:
				c += 1
		t += 1
	if c == K:
		ans = min(ans, t - s)
	v = A[s]
	if v <= K:
		u[v - 1] -= 1
		if u[v - 1] == 0:
			c -= 1
print(ans if ans < N + 1 else 0)


import sys
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
tmp = max(a)
tmp2 = max(tmp, n, k) + 1
chk = [0] * tmp2
for i in range(n):
	chk[a[i]] += 1
if 0 in chk[1:k + 1]:
	print(0)
	sys.exit()
right = n - 1
left = 0
L = []
while right < n:
	while chk[a[right]] > 1 or a[right] > k:
		chk[a[right]] -= 1
		right -= 1
	ln = right - left + 1
	L.append(ln)
	while chk[a[left]] > 1 or a[left] > k:
		chk[a[left]] -= 1
		left += 1
	ln = right - left + 1
	L.append(ln)
	chk[a[left]] -= 1
	left += 1
	while chk[a[left - 1]] == 0:
		right += 1
		if right >= n:
			break
		chk[a[right]] += 1
	ln = right - left + 1
	L.append(ln)
print(min(L))


def LI():
	return list(map(int, input().split()))

def II():
	return int(input())

def LS():
	return input().split()

def S():
	return input()

def LIR(n):
	return [LI() for i in range(n)]

def MI():
	return map(int, input().split())
(n, k) = MI()
a = LI()
l = 0
r = 0
ans = float('inf')
fl = [0 for i in range(k + 1)]
s = 0
if k == 1 and a[0] == 1:
	print(1)
	quit()
if a[0] <= k:
	fl[a[0]] = 1
	s = 1
while r < n - 1:
	r += 1
	if a[r] <= k:
		if not fl[a[r]]:
			s += 1
		fl[a[r]] += 1
	if s == k:
		while s == k:
			l += 1
			if a[l - 1] <= k:
				if fl[a[l - 1]] == 1:
					s -= 1
				fl[a[l - 1]] -= 1
		ans = min(ans, r - l + 2)
if ans == float('inf'):
	print(0)
	quit()
print(ans)


from collections import defaultdict
(N, K) = map(int, input().split())
A = [int(a) for a in input().split()]
(left, right, num) = (0, 0, 0)
ans = float('inf')
count = defaultdict(int)
while True:
	while right < N and num < K:
		if count[A[right]] == 0 and A[right] <= K:
			num += 1
		count[A[right]] += 1
		right += 1
	if num < K:
		break
	ans = min(ans, right - left)
	if count[A[left]] == 1 and A[left] <= K:
		num -= 1
	count[A[left]] -= 1
	left += 1
print(ans if ans != float('inf') else 0)