A survey satellite orbits above a ring of unmanned relay stations spaced around a perfectly circular patrol path. Every station continuously broadcasts a fixed numeric ID that never changes, and no two stations on the ring share the same ID. As the satellite completes lap after lap without ever stopping, its ground receiver appends the ID it hears at each moment to a single growing log, in the exact order the stations were passed. You are handed a finite prefix of that log — long enough to cover at least one full lap, and always cut off exactly at the end of a lap, never partway through one. Recover the one piece of information mission control actually needs: how many relay stations are on the ring.

Input format

• Line 1: a single integer m, the number of entries in the log.
• Line 2: m space-separated integers, the station IDs in the order the satellite radioed them, starting from an arbitrary station and continuing for one or more complete laps.

Output format

Print a single integer: the number of relay stations on the ring.

Constraints

• 1 <= m <= 1000
• Each logged ID is an integer in [1, 10^9].
• It is guaranteed that the true number of stations n satisfies 1 <= n <= 1000, that the log's first n entries are pairwise distinct (one per station), and that m is an exact positive-integer multiple of n — the log always ends exactly at a lap boundary and never partway through one.

6
5 9 2 5 9 2

3

4
7 7 7 7

1