G. Максимальное разнообразие

Задачу добавил: alef

Успешно сдано решений: 22

Ограничение по времени: 2 с

Ограничение по памяти: 256 Мб

Министр науки Фалалей, конечно, догадывался, что царь может пожелать хоть какую-нибудь функцию «Умного дворца» увидеть в работе как можно скорее. Но на то у него была хитрая задумка. На недавнем конгрессе инноваторов от королевства Ганса представляли «умный холодильник» и показывали, как он в интернет-магазине сам йогурты заказывает. Вид у него как у обычного холодильника, значит, сложного ничего нет, местные инженеры должны справиться. Ну а пока они разрабатывают, можно для царя один холодильник и за границей купить.

Как всегда некстати министр промышленности Силантий вопросы задавать начал. Ежели холодильник в королевстве Ганса произведён, так и йогурты он в королевстве Ганса будет заказывать. А как же быть с указом царя, согласно которому запрещено в царство ввозить продукты питания из других царств и королевств? Фалалей уверил, что проблемы никакой нет — холодильник перенастроить можно. Более того, это уже сделано, и даже новая функции от местных разработчиков добавлена: холодильник следит за сроками годности и обеспечивает максимальное разнообразие йогуртов.

В магазине есть $n$ видов йогуртов. Каждый вид йогурта имеет срок годности, который для удобства записан как количество дней, в течение которых этот йогурт ещё можно употреблять. Если срок годности $0$ — значит, йогурт надо непременно съесть сегодня, если $1$ — значит, крайний срок употребления — завтра, и т.д.

Царь съедает один йогурт в день.

Холодильник проанализирует сроки годности йогуртов и закажет не более одного йогурта каждого вида так, чтобы можно было съедать по одному йогурту в день, и срок годности йогурта позволял бы это безопасно сделать.

Ваша задача — по информации о йогуртах в магазине определить, сколько и какие именно йогурты следует приобрести, а также установить порядок, в котором их следует съесть.

Входные данные

В первой строке содержится целое число $n$ $(1 \leq n \leq 3 \cdot 10^{5})$ — количество видов йогуртов в магазине.

Во второй строке содержится $n$ целых чисел $d_{1}, d_{2}, \dots, d_{n}$ $(0 \leq d_{i} \leq 3 \cdot 10^{5}, i = 1, 2, \dots, n)$ , $d_{i}$ — срок годности йогурта вида $# i$ .

Выходные данные

В первой строке выведите целое число $k$ — количество йогуртов, которое будет приобретено.

Во второй строке выведите $k$ целых чисел — виды йогуртов в том порядке, в котором их следует съесть. Если возможно несколько вариантов ответа, выведите любой.

Пример

Входные данные

14
5 0 2 2 10 1 3 5 4 7 14 4 7 12

Выходные данные

11
2 4 8 7 12 1 13 10 11 14 5

Примечание

Поясним приведённый пример.

Йогурт $# 2$ имеет срок годности $0$ , и его можно съесть сегодня (в день $1$ ).

Йогурт $# 4$ имеет срок годности $2$ , и его можно съесть до дня $3$ включительно $(1 + 2 = 3)$ , а съедается он в день $2$ .

Йогурт $# 8$ имеет срок годности $5$ , так что его можно съесть до дня $6$ включительно, а по плану он будет съеден в день $3$ .

Йогурт $# 7$ имеет срок годности $3$ , и день $4$ — это последний день, когда его можно будет съесть (что и произойдёт).

Йогурт $# 12$ имеет срок годности $4$ ; как и предыдущий йогурт, он будет съеден в последний возможный день (в день $5$ ).

Йогурт $# 1$ имеет срок годности $5$ , так что он может быть съеден в день $6$ .

Йогурт $# 13$ имеет срок годности $7$ , и его можно съесть до дня $8$ включительно; он будет съеден в день $7$ .

Йогурт $# 10$ также имеет срок годности $7$ и будет съеден в день $8$ .

Йогурт $# 11$ имеет срок годности $14$ , а съеден будет в день $9$ .

Йогурт $# 14$ имеет срок годности $12$ и будет съеден в день $10$ .

Йогурт $# 5$ имеет срок годности $10$ и будет съеден в день $11$ .

Заметим, что это не единственно возможный ответ.

Сдать задачу

Задать вопрос жюри по этой задаче

Login:
Password:
	Забыли пароль?