26464번 - 2-LIS 다국어

You are given an integer sequence $A = (a_1, a_2, \dots , a_N)$. Find the length of the longest sequence $B = (b_1, b_2, \dots , b_N)$ which satisfies the following two conditions:

• $B$ is a subsequence of $A$
• $b_i < b_{i+2}$ for all $i$ ($1 ≤ i ≤ M-2$)

A subsequence of a sequence is a sequence obtained by removing zero or more elements from the original sequence and then concatenating the remaining elements without changing the order.

$N$

$a_1$ $a_2$ $\dots$ $a_N$

The first line consists of an integer $N$ between $1$ and $5\,000$, inclusive. This represents the number of elements in $A$.

The second line consists of $N$ integers between $1$ and $N$, inclusive. For each $i$ ($1 ≤ i ≤ N $), $a_i$ represents the $i$-th element of $A$.

Print the answer in a line.