题目背景

小强和阿米巴是好朋友。

题目描述

小强喜欢数列。有一天，他心血来潮，写下了三个长度均为 $n$ 的数列。

阿米巴也很喜欢数列。但是他只喜欢其中一种，波动数列。

阿米巴把他的喜好告诉了小强。小强便打算找出这三个数列内的最长波动数列。

也就是说，如果我们将三个数列记做 $a_{n,1},a_{n,2},a_{n,3}$，他必须要构造一个二元组序列：$(p_i,q_i)$，使得对于任何 $i>1$ 有：

• $p_i>p_{i-1}$。

• 若 $q_i=0$，$a_{p_i,q_i} \ge a_{p_{i-1},q_{i-1}}$。

• 若 $q_i=1$，$a_{p_i,q_i} \le a_{p_{i-1},q_{i-1}}$。

• 若 $q_i=2$，只要保持段内同向即可（就是对于连续的一段 $q_i=2$，要么都有 $a_{p_i,q_i} \ge a_{p_{i-1},q_{i-1}}$，要么都有 $a_{p_i,q_i} \le a_{p_{i-1},q_{i-1}}$。

小强希望这个二元组序列尽可能长。

提示：当 $q_i \not = q_{i-1}$ 时，数列的增减性由 $q_i$ 而非 $q_{i-1}$ 决定。

清晰版题目描述

小强拿到一个 $3 \times n$ 的数组，要在每一列选一个数（或者不选），满足以下条件：

1. 如果在第一行选，那它必须大于等于上一个数。

2. 如果在第二行选，那么必须小于等于上一个数。

3. 如果在第三行选，对于连续的一段在第三行选的数，必须满足方向相同（都小于等于上一个数或者都大于等于上一个数）。

输入格式

输入包含 $4$ 行。

第一行一个数 $n$，表示数列长度。

第 $2,3,4$ 行，每行 $n$ 个整数，分别表示三个数列。

输出格式

输出仅包含一个整数，即最长波动数列的长度。

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

6

提示

对于 $20\%$ 的数据，$n \le 10$，$m \le 1000$。

对于 $60\%$ 的数据，$n \le 1000$，$m \le 1000$。

对于 $100\%$ 的数据，$n \le 10^5$，$m \le 10^9$。

其中 $m=\max\{|a_i|\}$。

样例解释：

取第三行 $1,2,3$（增），然后取第一行 $6$（增），然后取第三行 $5,4$（减），长度为 $6$。