Background

C/C++/Python Postgraduate Group.

Problem Description

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.

Input Format

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 Format

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

10
1 3 2 4 1 2 3 4 3 1

8

Hint

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