## Yet Another Contest 4 P1 - Snap

View as PDF

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type

Josh and Nils are playing a variant of snap!

The game involves both Josh and Nils starting with cards each, where each of the total cards contains an integer between and . Then, in each of the rounds, Josh and Nils will remove the top card from their decks and place them face-up on the table at the same time. If the displayed cards are matching (have the same integer written on them), then whoever is first to yell "Snap!" receives one point.

Before the game, all cards are in a pile, with the -th card from the top having the integer written on it. First, as an umpire, you will cut the cards by removing cards from the top of the pile and moving them to the bottom of the pile, whilst preserving the order of the removed cards. Note that it is possible that , in which case no cards are moved. Then, Josh's deck will consist of the first cards of the pile in top-to-bottom order, and Nils' deck will consist of the next cards of the pile in top-to-bottom order.

To make the game more exciting, you wish to cut the cards optimally by carefully choosing the value of , such that the total number of rounds with matching cards is maximised. What is the maximum possible number of rounds with matching cards?

#### Input Specification

The first line of input contains a single integer .

The second line of input contains space-separated integers, .

#### Output Specification

On a single line, output the maximum possible number of rounds where the displayed cards have the same integers.

#### Sample Input

3
1 2 3 1 4 5

#### Sample Output

1

#### Explanation

Consider Josh choosing . After completing the cut, the pile of cards would have the integers from top to bottom.

Then, Josh's deck would have the integers from top to bottom, whilst Nils' deck would have the integers from top to bottom.

During the first round, Josh places a card with the integer , and Nils places a card with the integer . These cards do not match.

During the second round, Josh places a card with the integer , and Nils places a card with the integer . These cards match.

During the third round, Josh places a card with the integer , and Nils places a card with the integer . These cards do not match.

In total, there is round where the cards match. It can be shown that this is the maximum number of rounds for all possible values of .