Maximize Card Shredding

You are given an integer \(n\) and a sequence of \(n\) cards. The \(i\)-th card has a number \(A_i\). Initially the deck is empty. Then, for \(i = 1,2,\ldots,n\), you perform the following operation:

1. You take the \(i\)-th card and insert it to the deck, either at the left end or at the right end.
2. After the insertion, if there exist two cards in the deck that have the same number, you immediately remove from the deck the entire contiguous block spanning from the left occurrence to the right occurrence (including both cards) and send all these cards to the shredder.

The removal (or shredding) is triggered immediately after the insertion step. Note that if multiple duplicate pairs exist, you may assume that you can choose the one that maximizes the total number of cards removed. Your task is to determine the maximum number of cards that can be shredded (removed) by choosing the insertion sides optimally.

It can be shown that the optimal strategy shreds exactly \[ n - (\text{number of values that appear an odd number of times}) \] cards.

inputFormat

The input begins with an integer \(n\) \((1 \leq n \leq 10^5)\) indicating the number of cards.

The next line contains \(n\) integers \(A_1, A_2, \ldots, A_n\) \((1 \leq A_i \leq 10^9)\) representing the number on each card.

outputFormat

Output a single integer, which is the maximum number of cards that can be shredded using an optimal insertion strategy.

sample

3
1 1 1

2