루미 알고리즘

#1463골드Codforces

PO 2019 결선코딩출제 Simon Lindholm영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Nicolas wants to start a competitive fishing career in the codforces™ championships. There are a lot of different divisions to compete in, but since Nicolas is a new participant in codforces™ he must start in the lowest division (division 1). Nicolas goal is to as quickly as possible get to the highest division (division K) and win a fishing contest in it.

The codforces™ rules state that you may only gain a single division per contest, so he needs to perform at least one contest in each division. Nicolas is very confident, and thinks he will only need exactly one contest per division to get to the next division. When codforces™ has a contest, there's only a single division competing at a time, and two competitions never overlap in time. The contests also follow the same schedule each year.

Nicolas may start competing at codforces™ any day of the year. What he means by as fast as possible is that as few contests as possible should occur at codforces™ (independent of whether he competes in them or not) between the first contest he participates in and the first win Nicolas gets in the highest division. Help Nicolas to compute the number of competitions he needs.

Input

The first line of input contains two integers N and K (1 ≤ K ≤ N ≤ 10^6), the number of contests per year, and the number of divisions.

The next line contains the N integers x_1, …, x_N, (1 ≤ x_i ≤ K), the schedule of contests for a year. x_i is the division competing during the i'th contest counted from the start of a new year. Each division between 1 and K has at least one contest during the year.

Output

Output a single integer, the smallest number of contests that codforces™ needs to host between Nicolas's first contest and his first win in division K.

Scoring

Your solution will be tested on a set of test case groups. To get the points for a group, you need to pass all the test cases in the group.

GroupPointsConstraints
115N ≤ 10^2
220N ≤ 10^3
325N = K
440No further constraints

Explanation of sample 3

The fastest way for Nicolas to reach his target is to let his first contest be the second one for division 1 during the year. Then he waits for four contests to participate in the first division 2 contest in the year after. Then he waits for three contests to compete in division 3. Then he waits for five contests to compete in division 4. Finall he waits for two contests to compete in division 5. In total, it takes 1+(4+1)+(3+1)+(5+1)+(2+1) = 19 contests.

예제

예제 1

입력
3 3
3 2 1
출력
5

예제 2

입력
3 2
1 1 2
출력
2

예제 3

입력
7 5
2 1 1 4 3 2 5
출력
19

출처 표기

출처: Programmeringsolympiaden 2019년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.