Optimal Deque Game

A double‐ended queue contains n balls, each with a color. Two players, A and B, play a game as follows:

• Player A moves first and then the players alternate turns.
• On each turn, a player removes one ball from either the left end or the right end of the queue.
• If the color of the removed ball has not been removed before (i.e. it is the first time this color is taken), the player earns 1 point.
• The game ends when all balls have been removed.

Assuming that both A and B play optimally to maximize their own point total, determine the final score of player A. Note that every distinct color can contribute at most 1 point, and since there are only two players, under optimal play A will win the "prize" for roughly half of the distinct colors. In fact, if there are D distinct colors, then A’s final score will be ceil(D/2) (i.e. (D+1)//2 in integer arithmetic).

Example:

Input:  3
       1 2 3
Output: 2

inputFormat

The input consists of two lines:

1. The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of balls.
2. The second line contains n space‐separated integers, each representing the color of a ball. Colors may be any integer.

outputFormat

Output a single integer — the final score earned by player A when both players play optimally.

sample

1
5

1