题目描述

一个序列 $T = [t_1, t_2, \cdots, t_k]$ 是“山峰序列”当且仅当存在一个长度为 $m$（$m$ 可任意选）的下标对序列 $(l_1, r_1), (l_2, r_2), \cdots, (l_m, r_m)$ 满足：

• $l_1 = 1$ 且 $r_m = k$；
• $r_i > l_i$；
• $r_{i-1} + 1 = l_i$；
• $r_i - l_i \equiv 0 \pmod{2}$ 且 $t_{(l_i + r_i)/2}$ 是序列 $T$ 在区间 $[l_i, r_i]$ 中的最大值；
• 序列 $T$ 在区间 $[l_i, \dfrac{l_i + r_i}{2}]$ 严格单调递增，在区间 $[\dfrac{l_i + r_i}{2}, r_i]$ 严格单调递减。

给定一个长度为 $n$ 的整数数组 $[a_1, a_2, \cdots, a_n]$，求其最长的子序列 $T$ 满足 $T$ 是“山峰序列”，输出其长度，若不存在则输出 0。

说明：下标对序列 $(l_i, r_i)$ 基于子序列 $T$ 的下标，$T$ 的下标从 1 开始。

输入格式

输入的第一行包含一个正整数 $n$。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

10
1 3 2 4 1 2 3 4 3 1

8

解释 #1

可取子序列 $T = [1, 3, 2, 2, 3, 4, 3, 1]$，其长度为 8 且为一个“山峰序列”，下标对序列为 $(1, 3), (4, 8)$。

数据范围

• 对于 $20\%$ 的评测用例，$1 \le n \le 50$；
• 对于 $40\%$ 的评测用例，$1 \le n \le 200$；
• 对于所有评测用例，$1 \le n \le 2000$，$0 \le a_i \le 10^6$。