Longest Valid Rhymed Poem Subsequence

Huang Yaoshi, famous not only for his martial arts but also for his love of music and poetry, composed a poem of N lines. Unfortunately, the poem does not follow a consistent classical rhyming scheme. Ancient Chinese poetry requires that every group of four consecutive lines (a quatrain) must follow one of the following rhyme patterns (where A and B denote two distinct rhymes):

• \(AABB\)
• \(ABAB\)
• \(ABBA\)
• \(AAAA\)

Each line of the poem is marked with a number representing its rhyme. Lines with the same number have the same rhyme. Huang Yaoshi now wishes to remove some lines (without changing the original order) such that the remaining poem can be partitioned into quatrains (groups of four consecutive lines) that all follow one of the aforementioned patterns. Note that any leftover lines that do not form a complete quatrain are not allowed.

Your task is to determine the maximum number of lines that can be retained to form a valid poem.

Rhyme Pattern Validity

For a group of four lines with rhyme numbers \(a, b, c, d\), the group is valid if and only if at least one of the following conditions is satisfied:

• \(a=b\) and \(c=d\) and \(a \neq c\)    (AABB)
• \(a=c\) and \(b=d\) and \(a \neq b\)    (ABAB)
• \(a=d\) and \(b=c\) and \(a \neq b\)    (ABBA)
• \(a=b=c=d\)    (AAAA)

inputFormat

The first line contains a positive integer \(N\) (the number of lines in the poem). The second line contains \(N\) integers, where the \(i\)-th integer represents the rhyme code of the \(i\)-th line.

outputFormat

Output a single integer, the maximum number of lines that can be retained so that the remaining lines (when partitioned into consecutive groups of four) each form a valid quatrain according to the rules above.

sample

4
1 1 2 2

4