영화 정보 캐시의 최소 크기

문제

영화관 예매 시스템은 상영 정보를 조회할 때마다 영화 번호로 정보를 찾는다. 시스템 앞단에는 영화 정보를 최대 K개까지 담는 LRU 캐시가 있다. 조회 요청이 들어왔을 때 그 영화가 캐시에 있으면 적중이고, 해당 영화는 가장 최근에 쓴 항목이 된다. 캐시에 없으면 미스이며, 그 영화를 캐시에 가장 최근에 쓴 항목으로 넣는다. 이때 캐시에 이미 K개가 들어 있었다면 가장 오래전에 사용된 영화 하나를 먼저 내보낸다. 캐시는 처음에 비어 있다. 하루 동안의 조회 요청이 N개 순서대로 주어진다. 점검 목표는 적중 횟수가 H번 이상이 되는 것이다. 이 목표를 이루는 가장 작은 캐시 크기 K(K ≥ 1, 정수)를 구하라. 어떤 K로도 적중 횟수가 H번 이상이 될 수 없다면 -1 을 출력한다. 캐시 크기를 늘려도 적중 횟수가 줄어들지는 않는다는 점이 알려져 있다.

입력

첫 줄에 N 과 H 가 공백으로 구분되어 주어진다. 둘째 줄에 조회한 영화 번호 N개가 공백으로 구분되어 순서대로 주어진다. 1 ≤ N ≤ 200,000, 1 ≤ H ≤ N, 영화 번호는 1 이상 1,000,000,000 이하의 정수이다.

출력

적중 횟수를 H번 이상으로 만드는 가장 작은 K 를 한 줄에 출력한다. 불가능하면 -1 을 출력한다.

7 2
1 2 3 1 2 3 1

3

6 3
1 1 2 1 2 2

2

4 1
1 2 3 4

-1

출처: Devin.KR 자체 제작