사격 게임장

공원의 사격 게임장은 단순하면서도 까다로운 놀이기구다. 가로로 놓인 횃대 하나에 오리가 한 줄로 앉아 있다. 오리의 종이 모두 같지는 않으며, 서로 쉽게 구별되는 여러 종이 섞여 있기도 하다.

사격은 라운드 단위로 진행된다. 한 라운드에서 사수는 두 발을 쏘고, 한 발은 오리를 최대 한 마리 맞힌다. 같은 종의 오리 두 마리를 맞힌 라운드는 좋은 라운드다. 맞힌 오리가 두 마리에 못 미치거나 서로 다른 종의 오리 두 마리를 맞힌 라운드는 나쁜 라운드다.

사수는 다음 두 조건을 모두 만족할 때만 라운드를 요청할 수 있다.

• 횃대에 같은 종의 오리가 두 마리 이상 남아 있다.
• 이번 사격의 첫 라운드를 요청하거나(횃대가 오리로 가득 차 있다), 직전 라운드가 좋은 라운드였다.

더 이상 라운드를 요청할 수 없으면 사격이 끝나고 성적을 매긴다.

소리 효과를 키우고 난이도를 올리려고 장치 하나가 더 붙어 있다. 좋은 라운드가 나오면 장치가 곧바로 횃대의 오리 수를 줄인다. 그 라운드에서 맞힌 두 오리 사이에 앉아 있지 않던 오리는 자동 총이 모두 떨어뜨린다. 맞힌 두 마리도 함께 떨어지므로, 횃대에는 두 마리 사이에 있던 오리만 남는다. 남는 오리가 크게 줄어 사격이 그 자리에서 끝나기도 한다.

사격의 목표는 좋은 라운드를 연속으로 최대한 많이 쏘는 것이다. 각 라운드에서 어느 두 마리를 고르는지에 따라 사격이 이어지는 길이가 달라진다. 주어진 배치에서 얻을 수 있는 좋은 라운드의 최대 개수를 구하라.

입력은 여러 개의 테스트 케이스로 이루어지고 파일 끝까지 이어진다. 각 테스트 케이스는 두 줄이다. 첫째 줄에 횃대에 앉은 오리의 수 $N$ ($1 \le N \le 5000$)이 주어진다. 둘째 줄에 $N$개의 양의 정수 $D_i$ ($1 \le D_i \le 10^4$)가 공백으로 구분되어 주어진다. $i$번째 값은 왼쪽에서 $i$번째 오리의 종을 나타낸다. 같은 값은 같은 종, 다른 값은 다른 종이다.

테스트 케이스는 20개 이하이고, 모든 테스트 케이스의 $N$ 합은 20000 이하다.

각 테스트 케이스마다 연속으로 쏠 수 있는 좋은 라운드의 최대 개수를 한 줄에 하나씩 출력한다.