Pizza Happy

Limits: 3 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Turtles eat exclusively pizza. They decided that a day is happy if during this day there was no type of pizza that they ate only once.

Splinter brought \(n\) boxes of pizza of various types, forming the order of pizzas in which they must be eaten. It is known that after eating all \(n\) pizzas, the turtles will have a happy day — that is, in the entire sequence there is no type that appears exactly once.

Donatello suggested splitting the initial sequence into smaller sequences, and each such part will be eaten on a separate day.

Help the turtles: calculate the maximum number of happy days they can split their pizza eating into, by dividing the initial sequence into contiguous parts such that each part ensures a happy day.

Input

The first line gives a single number \(n\) — the number of pizzas brought by Splinter.

The second line gives \(n\) integers \(a_i\) — the types of pizza.

Output

Output a single number — the maximum number of happy days.

Constraints

\(2 \le n \le 5 \cdot 10^5\),

\(1 \le a_i \le 10^9\).

Samples