영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
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.
| Group | Points | Constraints |
|---|---|---|
| 1 | 20 | v < a_1 < a_2 < … < a_N |
| 2 | 20 | a_1 > a_2 > … > a_N |
| 3 | 17 | N = 2 |
| 4 | 43 | No 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