Star Trek

An expedition is about to set off on a new-generation spaceship. It will visit $N$ planets of a star system in order, from planet Earth to planet Victory. The planets are numbered $1$ to $N$ in the order they are visited; Earth has number $1$ and Victory has number $N$.

To fly between planets, the ship may use any type of fuel that exists in the star system. Before the expedition starts, the ship is on planet Earth and its tank is empty. The existing fuel types are numbered with integers, and on planet $i$ the ship can refuel only with fuel of type $a_i$. When visiting planet $i$, the ship can refuel by emptying the tank of whatever fuel it holds and filling it with fuel of type $a_i$.

At each planet the refueling station is built so that the tank receives exactly as much fuel as is needed to fly to the next planet with fuel of the same type. If that fuel type never occurs again, refueling at this planet is impossible. In other words, after refueling on planet $i$, the fuel is enough to visit planets $(i + 1)$ through $j$ inclusive, where $j$ is the smallest planet number such that $j > i$ and $a_j = a_i$. To continue the expedition beyond planet $j$, the ship must refuel again on one of these planets.

Write a program that, given the fuel types on the planets, determines the minimum number of refuelings required for the expedition.

The first line of the input file contains the number $N$ ($2 \leqslant N \leqslant 300\,000$), the number of planets.

The second line of the input file contains $N$ integers $a_1, a_2, \ldots, a_N$ ($1 \leqslant a_i \leqslant 300\,000$), the fuel types on the planets.

In the first line of the output file, print the single number $K$, the minimum number of refuelings that must be performed.

In the second line, print $K$ numbers separated by spaces: the numbers of the planets where refueling is required. Print the planet numbers in the order in which the refuelings occur.

If there are several solutions with the minimum number of refuelings, print any of them. If no solution exists, print the number $0$.

• $N \le 300\,000$