Description

Xiao Qiang likes sequences. One day, on a whim, he wrote down three sequences, each of length $n$.

Amiba also likes sequences, but he only likes one type, the wave sequence.

Amiba told Xiao Qiang about his preference. Xiao Qiang plans to find the longest wave sequence within these three sequences.

That is, if we denote the three sequences as $a_{n,1},a_{n,2},a_{n,3}$, he must construct a sequence of ordered pairs $(p_i,q_i)$ such that for any $i>1$:

• $p_i>p_{i-1}$.
• If $q_i=0$, then $a_{p_i,q_i} \ge a_{p_{i-1},q_{i-1}}$.
• If $q_i=1$, then $a_{p_i,q_i} \le a_{p_{i-1},q_{i-1}}$.
• If $q_i=2$, it only needs to keep the same direction within a segment (that is, for a contiguous segment with $q_i=2$, either all satisfy $a_{p_i,q_i} \ge a_{p_{i-1},q_{i-1}}$, or all satisfy $a_{p_i,q_i} \le a_{p_{i-1},q_{i-1}}$).

Xiao Qiang wants this sequence of ordered pairs to be as long as possible.

Hint: When $q_i \not = q_{i-1}$, the monotonicity is determined by $q_i$, not by $q_{i-1}$.

Clear version of the problem statement

Xiao Qiang gets a $3 \times n$ array. In each column, choose one number (or choose none), subject to the following conditions:

1. If you choose from the first row, it must be greater than or equal to the previous number.
2. If you choose from the second row, it must be less than or equal to the previous number.
3. If you choose from the third row, then for any contiguous segment of numbers chosen from the third row, the directions must be the same (either all are less than or equal to the previous number, or all are greater than or equal to the previous number).

Input Format

The input contains $4$ lines.

The first line contains an integer $n$, the length of the sequences.

The $2$nd, $3$rd, and $4$th lines each contain $n$ integers, representing the three sequences, respectively.

Output Format

Output a single integer, the length of the longest wave sequence.

6
1 2 3 6 5 4
5 4 3 7 8 9
1 2 3 6 5 4

6

Hint

Constraints:

• For $20\%$ of the testdata, $n \le 10$, $m \le 1000$.
• For $60\%$ of the testdata, $n \le 1000$, $m \le 1000$.
• For $100\%$ of the testdata, $n \le 10^5$, $m \le 10^9$.

Here $m=\max\{|a_i|\}$.

Sample explanation:

Take 1, 2, 3 from the third row (increasing), then take 6 from the first row (increasing), then take 5, 4 from the third row (decreasing), for a length of 6.

Translated by ChatGPT 5