一个 3 行 $n$ 列的矩阵，要从左往右在每一列依次选一个数（或者不选），满足以下条件：
-
如果在第一行选，那么必须大于等于上一个被选择的数（如果不存在上一个数则没有这个限制）；
-
如果在第二行选，那么必须小于等于上一个被选择的数（如果不存在上一个数则没有这个限制）；
-
如果在第三行选，那么在选出的数构成的序列 $s_1,s_2, \dots, s_k$ 中，若对于连续的一段 $s_l,s_{l+1},\cdots,s_{r}$ 其均为第三行选出的数，那么需要满足 $s_{l-1} \leq s_{l} \leq s_{l+1} \leq \cdots \leq s_{r}$ 或 $s_{l-1} \geq s_{l} \geq s_{l+1} \geq \cdots \geq s_{r}$（即单调性方向相同）。
请求出能选择的数的最大个数。
【样例解释】
其中一种方案是取第三行 1，2，3，然后取第一行 6，然后取第三行 5，4，长度为 6。
记 $m$ 表示矩阵中所有数的最大的绝对值。
对于 $20\%$ 的数据，$ n \leq 10 , m \leq 1000 $ ；
对于 $60\%$ 的数据，$ n \leq 1000 , m \leq 1000$
对于 $100\%$ 的数据，$1\leq n \leq 10^5 , 0 \leq m \leq 10^9$。