cho.sh

Shooting Gallery

A row of ducks, each with a species; a good round hits two ducks of the same species and keeps only the ducks strictly between them, and rounds continue while same-species pairs remain. Find the longest possible run of good rounds.

Hard8Dynamic programmingArrayIntervalsTwo pointersInterviewNo attempts yetTime limit2sMemory limit512 MB

Problem

The shooting gallery in the park is simple and tricky at the same time. A row of ducks sits on one horizontal perch. The ducks are not all of the same species, and several species that are easy to tell apart can be mixed together.

Shooting proceeds in rounds. In each round the shooter fires two shots, and each shot hits at most one duck. A round is a good round if the shooter hits two ducks of the same species. A round is a bad round if the shooter hits fewer than two ducks, or hits two ducks of different species.

The shooter can ask for a round only when both of these conditions hold:

  • At least two ducks of the same species are left on the perch.
  • This is the first round of the shooting (the perch is full of ducks), or the previous round was a good round.

When the shooter cannot ask for another round, the shooting ends and the result is scored.

One more device is attached, to make the noise louder and the game harder. Every time a good round happens, the device immediately reduces the number of ducks on the perch. An automatic gun shoots down every duck that was not sitting between the two ducks hit in that round. The two ducks that were hit fall as well, so only the ducks that sat between them stay on the perch. Sometimes so few ducks are left that the shooting ends right there.

The goal is to fire as many good rounds in a row as possible. The choice of the two ducks in each round decides how long the shooting lasts. Given the arrangement, find the largest number of good rounds that can be fired.

Input

The input holds several test cases and continues to the end of the file. Each test case takes two lines. The first line has the number of ducks on the perch, NN (1≤N≤50001 \le N \le 5000). The second line has NN positive integers DiD_i (1≤Di≤1041 \le D_i \le 10^4), separated by spaces. The ii-th value is the species of the ii-th duck from the left. Equal values mean the same species, different values mean different species.

There are at most 20 test cases, and the sum of NN over all test cases is at most 20000.

Output

For each test case, print one line with the largest number of good rounds that can be fired in a row.