There is unrest in the Galactic Senate. Several thousand solar systems have declared their intentions to leave the Republic. Master Heidi needs to select the Jedi Knights who will go on peacekeeping missions throughout the galaxy. It is well-known that the success of any peacekeeping mission depends on the colors of the lightsabers of the Jedi who will go on that mission. 

Heidi has n Jedi Knights standing in front of her, each one with a lightsaber of one of m possible colors. She knows that for the mission to be the most effective, she needs to select some contiguous interval of knights such that there are exactly k_1 knights with lightsabers of the first color, k_2 knights with lightsabers of the second color, ..., k_{m} knights with lightsabers of the m-th color.

However, since the last time, she has learned that it is not always possible to select such an interval. Therefore, she decided to ask some Jedi Knights to go on an indefinite unpaid vacation leave near certain pits on Tatooine, if you know what I mean. Help Heidi decide what is the minimum number of Jedi Knights that need to be let go before she is able to select the desired interval from the subsequence of remaining knights.


-----Input-----

The first line of the input contains n (1 ≤ n ≤ 2·10^5) and m (1 ≤ m ≤ n). The second line contains n integers in the range {1, 2, ..., m} representing colors of the lightsabers of the subsequent Jedi Knights. The third line contains m integers k_1, k_2, ..., k_{m} (with $1 \leq \sum_{i = 1}^{m} k_{i} \leq n$) – the desired counts of Jedi Knights with lightsabers of each color from 1 to m.


-----Output-----

Output one number: the minimum number of Jedi Knights that need to be removed from the sequence so that, in what remains, there is an interval with the prescribed counts of lightsaber colors. If this is not possible, output  - 1.


-----Example-----
Input
8 3
3 3 1 2 2 1 1 3
3 1 1

Output
1

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Sorting

Amortized analysis


Solutions:
INF = 1 << 60
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
Constraint = [0] + list(map(int, input().split()))
pos = 0
satisfied_color = 0
for i in range(1, m + 1):
	if Constraint[i] == 0:
		satisfied_color += 1
GETCOLOR = [0] * (n + 1)
ans = INF
waste = 0
for i in range(n):
	while satisfied_color < m and pos < n:
		now_color = a[pos]
		GETCOLOR[now_color] += 1
		if GETCOLOR[now_color] == Constraint[now_color]:
			satisfied_color += 1
		elif GETCOLOR[now_color] > Constraint[now_color]:
			waste += 1
		pos += 1
	if satisfied_color == m:
		ans = min(ans, waste)
	removed_color = a[i]
	if GETCOLOR[removed_color] > Constraint[removed_color]:
		GETCOLOR[removed_color] -= 1
		waste -= 1
		continue
	elif GETCOLOR[removed_color] == Constraint[removed_color]:
		GETCOLOR[removed_color] -= 1
		satisfied_color -= 1
if ans < INF:
	print(ans)
else:
	print(-1)


from collections import defaultdict
(n, m) = list(map(int, input().split()))
ns = list(map(int, input().split()))
ms = list(map(int, input().split()))
summs = sum(ms)
target = {i: m for (i, m) in enumerate(ms, 1)}
remain = set((i for (i, m) in list(target.items()) if m != 0))
count = defaultdict(int)
a = 0
b = 0
while remain and b < n:
	count[ns[b]] += 1
	if ns[b] in remain and target[ns[b]] <= count[ns[b]]:
		remain.remove(ns[b])
	b += 1
if remain:
	print(-1)
else:
	ans = b - summs
	while b <= n:
		if remain:
			if b >= n:
				break
			count[ns[b]] += 1
			if ns[b] in remain and target[ns[b]] <= count[ns[b]]:
				remain.remove(ns[b])
			b += 1
		else:
			count[ns[a]] -= 1
			if target[ns[a]] > count[ns[a]]:
				remain.add(ns[a])
			else:
				ans = min(ans, b - a - 1 - summs)
			a += 1
	print(ans)


from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
from collections import deque
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
brr = list(map(int, input().split()))
sum_brr = sum(brr)
lst = [[] for i in range(m + 1)]
for i in range(n):
	lst[arr[i]].append(i)
maxi_indx = -1
for i in range(1, m + 1):
	if len(lst[i]) < brr[i - 1]:
		print(-1)
		exit()
	if lst[i] and brr[i - 1]:
		maxi_indx = max(maxi_indx, lst[i][brr[i - 1] - 1])
flag = 0
n_lst = [[] for i in range(m + 1)]
mini_indx = float('inf')
if flag == 1:
	print(-1)
	exit()
for i in range(m + 1):
	v = bisect_right(lst[i], maxi_indx)
	n_lst[i] = lst[i][:v]
for i in range(m + 1):
	n_lst[i] = deque(n_lst[i])
for i in range(m):
	while len(n_lst[i + 1]) > brr[i]:
		n_lst[i + 1].popleft()
he = []
for i in range(m + 1):
	for j in n_lst[i]:
		heappush(he, [j, i])
		mini_indx = min(mini_indx, j)
mini = maxi_indx - mini_indx + 1
for i in range(maxi_indx + 1, n):
	if n_lst[arr[i]]:
		q = n_lst[arr[i]].popleft()
		n_lst[arr[i]].append(i)
		heappush(he, [i, arr[i]])
		while he[0][0] < n_lst[he[0][1]][0]:
			heappop(he)
		mini = min(mini, i - he[0][0] + 1)
print(mini - sum_brr)


(n, m) = list(map(int, input().split()))
arr = list(map(int, input().split()))
marr = list(map(int, input().split()))
f = [0] * (m + 1)
(cnt, i) = (0, 0)
valid = sum(marr)
while i < n:
	f[arr[i]] += 1
	if f[arr[i]] <= marr[arr[i] - 1]:
		cnt += 1
	if cnt == valid:
		break
	i += 1
if i == n:
	print(-1)
else:
	ans = i + 1 - valid
	(s, e) = (0, i)
	while e < n:
		while f[arr[s]] > marr[arr[s] - 1]:
			f[arr[s]] -= 1
			s += 1
		ans = min(e - s + 1 - valid, ans)
		e += 1
		if e < n:
			f[arr[e]] += 1
	print(ans)


import random, math
from copy import deepcopy as dc
from bisect import bisect_left, bisect_right

def solution(li, li1):
	freq = {}
	for i in range(len(li1)):
		if li1[i]:
			freq[i + 1] = li1[i]
	maxi = len(li)
	i = 0
	j = 0
	req = dc(freq)
	cur_freq = [0] * (len(li1) + 1)
	flag = False
	while i < len(li):
		while len(req) and j < len(li):
			cur_freq[li[j]] += 1
			if li[j] in req:
				req[li[j]] -= 1
				if req[li[j]] <= 0:
					del req[li[j]]
			j += 1
		if len(req):
			break
		flag = True
		maxi = min(maxi, j - i)
		cur_freq[li[i]] -= 1
		if li[i] in freq and cur_freq[li[i]] < freq[li[i]]:
			req[li[i]] = req.get(li[i], 0) + 1
		i += 1
	if not flag:
		return -1
	return maxi - sum(li1)

def input_test():
	(a, b) = map(int, input().strip().split(' '))
	li = list(map(int, input().strip().split(' ')))
	li1 = list(map(int, input().strip().split(' ')))
	out = solution(li, li1)
	print(out)

def test():
	pass
input_test()


(n, m) = map(int, input().split())
c = list(map(int, input().split()))
k = list(map(int, input().split()))
p = [0] * m
c = [i - 1 for i in c]
s = sum(k)
cnt = k.count(0)
l = 0
r = 0
while r < n and cnt < m:
	p[c[r]] += 1
	if p[c[r]] == k[c[r]]:
		cnt += 1
	r += 1
if cnt != m:
	print(-1)
	return
ans = r - l
while l < n:
	p[c[l]] -= 1
	while r < n and p[c[l]] < k[c[l]]:
		p[c[r]] += 1
		r += 1
	if p[c[l]] >= k[c[l]]:
		ans = min(ans, r - l - 1)
	elif r == n:
		break
	l += 1
print(ans - s)


(n, m) = map(int, input().split())
c = list(map(int, input().split()))
k = list(map(int, input().split()))
p = [0] * m
c = [o - 1 for o in c]
s = sum(k)
ok = k.count(0)
i1 = 0
i2 = 0
while i2 < n and ok < m:
	p[c[i2]] += 1
	if p[c[i2]] == k[c[i2]]:
		ok += 1
	i2 += 1
if ok != m:
	print(-1)
	exit(0)
ans = i2 - i1
while i1 < n:
	p[c[i1]] -= 1
	while i2 < n and p[c[i1]] < k[c[i1]]:
		p[c[i2]] += 1
		i2 += 1
	if p[c[i1]] >= k[c[i1]]:
		ans = min(ans, i2 - i1 - 1)
	elif i2 == n:
		break
	i1 += 1
print(ans - s)