First Book Out of Stock

You are given a sequence of book sales transactions. Each transaction is represented by an integer identifier of the book. A book is considered out of stock as soon as it is sold more than once. Your task is to determine the identifier of the first book that becomes out of stock.

If no book is sold twice, output None.

Note: The input consists of an integer n and a sequence of n integers. The solution should process the sales in the order given and detect the first repetition.

The problem can be formalized as follows:

$$\text{Find the smallest index } i \text{ such that } \exists\, j < i \text{ with } sales[i] = sales[j]. $$

inputFormat

The input is read from standard input and has the following format:

• The first line contains an integer n denoting the number of sales transactions.
• The second line contains n space-separated integers representing the book identifiers sold in order.

outputFormat

Output a single line to the standard output. Print the identifier of the first book that becomes out of stock. If no book becomes out of stock (i.e., no book is sold more than once), output None (without quotes).

## sample

5
1 2 1 3 2

1