ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Contest is over

C. Shortest Subchain

Time limit: 1.0 second
Memory limit: 64 MB
A chain p is given in a directed graph without loops or multiple edges. It is required to specify its subchain q such that
• the initial and final vertices of the chains p and q coincide;
• the edges in the chain q are in the same order as in the chain p;
• the chain q has the minimal possible number of edges under the given conditions.

Input

The chain p is given by the list of its vertices. The first line contains the number n of vertices in the list, 2 ≤ n ≤ 100000 (thus, the length of the chain is n−1). The following lines contain n numbers of vertices (they are integers in the range from 1 to 10000). The numbers are separated by spaces or linebreaks. No two successive vertices in the list coincide.

Output

Output the vertices of the chain q by giving their numbers separated by a space. Chain q may consist of single a vertex.

Sample

inputoutput
```9
1 2 7 3 2
8 4 8 5
```
```1 2 8 5
```
Problem Author: Vladimir Yakovlev (idea by Magaz Asanov)
Problem Source: NEERC 2008, Eastern subregion quarterfinals
To submit the solution for this problem go to the Problem set: 1651. Shortest Subchain