P1684 Trial

Everyone knows that Huang Yaoshi not only has superb martial arts, but also loves music and poetry. Seeing that a new guest has arrived on Peach Blossom Island, and that you did not enter by true martial arts, he decided to make things difficult for you. He wrote a poem with $N$ lines. Unfortunately, these lines do not rhyme, but Huang Yaoshi really wants to follow the rhyming rules of classical poetry. The poem is divided into several stanzas, each of which has four lines. Every line has a rhyme. Suppose $A$ and $B$ are two different rhymes; then the rhyme scheme of each four-line stanza can only be one of `AABB`, `ABAB`, `ABBA`, or `AAAA`. Huang Yaoshi numbered the rhymes of all lines; lines with the same number have the same rhyme. Now he wants to delete some lines so that the remaining lines can be partitioned into four-line stanzas that follow the rhyming rules, and the order of lines cannot be changed. The question is: how do you find the longest poem that satisfies the conditions?

The first line contains an integer $N$ ($1 \le N \le 4000$), the number of lines in the poem written by Huang Yaoshi. The second line contains $N$ integers, representing the rhyme of each line. These numbers are positive and do not exceed $10^9$, and each number is separated by a single space.

Output a single integer k, the maximum number of four-line stanzas that Huang Yaoshi can obtain.

Hint: By deleting the 3rd, 6th, and 13th lines, the poem can be divided into 3 four-line stanzas: - 1, 2, 4, 5. - 7, 8, 9, 10. - 11, 12, 14, 15. Translated by ChatGPT 5