P15442 [Lanqiao Cup 2025 National Postgraduate Group] Mountain Peak Subsequence

C/C++/Python Postgraduate Group.

A sequence $T = [t_1, t_2, \cdots, t_k]$ is a “mountain peak sequence” if and only if there exists an index-pair sequence of length $m$ ($m$ can be chosen arbitrarily), $(l_1, r_1), (l_2, r_2), \cdots, (l_m, r_m)$, such that: - $l_1 = 1$ and $r_m = k$. - $r_i > l_i$. - $r_{i-1} + 1 = l_i$. - $r_i - l_i \equiv 0 \pmod{2}$ and $t_{(l_i + r_i)/2}$ is the maximum value of sequence $T$ on the interval $[l_i, r_i]$. - Sequence $T$ is strictly increasing on the interval $[l_i, \dfrac{l_i + r_i}{2}]$, and strictly decreasing on the interval $[\dfrac{l_i + r_i}{2}, r_i]$. Given an integer array of length $n$, $[a_1, a_2, \cdots, a_n]$, find the longest subsequence $T$ such that $T$ is a “mountain peak sequence”, and output its length. **Note**: The index-pair sequence $(l_i, r_i)$ is based on the indices of the subsequence $T$, and the indices of $T$ start from 1.

The first line contains a positive integer $n$. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$, separated by one space.

Output one line containing one integer, which is the answer.

### Sample Explanation You can take the subsequence $T = [1, 3, 2, 1, 2, 4, 3, 1]$. Its length is 8 and it is a “mountain peak sequence”. The index-pair sequence is $(1, 3), (4, 8)$. ### Test Case Scale and Conventions For $20\%$ of the test cases, $1 \le n \le 50$. For $40\%$ of the test cases, $1 \le n \le 200$. For all test cases, $1 \le n \le 2000$, $0 \le a_i \le 10^6$. # Input Format # Output Format Translated by ChatGPT 5