Автор: | Жюри ROI-2013 | Ограничение времени: | 3 сек | |
Входной файл: | expedition.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | expedition.out |
Экспедиция готовится отправиться в путь на космическом корабле нового поколения. Планируется последовательно посетить N планет звёздной системы — от планеты Земля до планеты Победа. Планеты пронумерованы от 1 до N в порядке их посещения, Земля имеет номер 1, а Победа — номер N.
Для перелёта между планетами корабль может использовать любой тип топлива, существующий в звёздной системе. Перед началом экспедиции корабль находится на планете Земля, и бак корабля пуст. Существующие типы топлива пронумерованы целыми числами, на планете с номером i можно заправиться только топливом типа ai. При посещении i-й планеты можно заправиться, полностью освободив бак от имеющегося топлива и заполнив его топливом типа ai.
На каждой планете станция заправки устроена таким образом, что в бак заправляется ровно столько топлива, сколько потребуется для перелёта до следующей планеты с топливом такого же типа. Если далее такой тип топлива не встречается, заправляться на этой планете невозможно. Иначе говоря, после заправки на i-й планете топлива хватит для посещения планет от (i + 1)-й до j-й включительно, где j — минимальный номер планеты, такой что j > i и aj = ai. Для продолжения экспедиции дальше j-й планеты корабль необходимо снова заправить на одной из этих планет.
Требуется написать программу, которая по заданным типам топлива на планетах определяет минимальное количество заправок, требуемых для экспедиции.
В первой строке входного файла записано число N — количество планет.
Во второй строке входного файла записано N целых чисел a1, a2, …, aN — типы топлива на планетах.
В первой строке выходного файла выведите единственное число K — минимальное количество заправок, которые нужно произвести.
Во второй строке выведите K чисел, разделённых пробелами, — номера планет, на которых требуется заправиться. Номера планет требуется выводить в порядке времени заправок.
Если решений с минимальным количеством заправок несколько, выведите любое из них. Если решения не существует, выведите число 0.
2 ≤ N ≤ 300 000;
1 ≤ ai ≤ 300 000;
№ | Входной файл (expedition.in ) |
Выходной файл (expedition.out ) |
---|---|---|
1 |
|
|
2 |
|
|