루미 알고리즘

#1634골드Duplantis

PO 2026 결선코딩출제 Nils Gustafsson, Björn Martinsson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Duplantis has a problem. He can't decide if he should beat as many world records as possible, or set one world record that is as good as possible.

At the moment, his world record is v centimeters. Duplantis has predicted how well he will perform in the remaining N competitions of his career. To do that, he calculated the positive integers a_1, a_2, …, a_N. The number a_i means that Duplantis can jump between 0 and a_i centimeters in the ith competition. He can decide freely how high he should jump in a competition, as long as the height is an integer between 0 and a_i centimeters.

In order to beat the world record, Duplantis has to jump strictly higher than his previous world record. It is only allowed to beat at most one world record in the same competition. In pole vaulting, you always jump an integer number of centimeters.

Your task is to calculate r, the maximum number of additional world records that Duplantis can beat. You should also find the numbers b_1, b_2, …, b_r, where b_i is the highest possible final world record given that Duplantis beats exactly i more world records.

Input

The first line contains two integers N and v (1 ≤ N ≤ 3 · 10^5, 0 ≤ v ≤ 10^9), where N is the number of competitions and v is Duplantis' current world record.

The second line contains N integers a_1, a_2, …, a_N (0 ≤ a_i ≤ 10^9).

Output

On the first line, print r, the maximum number of additional world records Duplantis can beat.

On the second line, print the r numbers b_1, b_2, …, b_r, where b_i is the maximum possible final world record if Duplantis beats exactly i more world records.

Note that r can be zero, in that case you should leave the second line empty (it is also OK to not print this empty line).

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
120v < a_1 < a_2 < … < a_N
220a_1 > a_2 > … > a_N
317N = 2
443No additional constraints.

Explanation of Samples

In the first example, Duplantis can beat at most 3 more world records. He can for example jump 635 in the first competition, 640 in the second, and finally 650 in the fourth competition. In the other competitions he can do whatever he wants. On the other hand, if he only beats one more world record, then he can achieve a height of 700 centimeters by jumping as high as possible in the first competition.

In the second example it unfortunately seems like Duplantis has already peaked, and cannot beat any more world records.

예제

예제 1

입력
6 630
700 645 620 650 631 100
출력
3
700 650 650

예제 2

입력
3 630
630 610 580
출력
0

출처 표기

출처: Programmeringsolympiaden 2026년 결선 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.