Longest Increasing Subsequence After Removal

Given an integer \(n\) and a sequence of \(n\) integers \(b_1, b_2, \ldots, b_n\), your task is to remove exactly one element such that the remaining sequence has the longest strictly increasing subsequence.

For a given sequence \(a_1, a_2, \ldots, a_m\), a strictly increasing subsequence is a subsequence \(a_{i_1}, a_{i_2}, \ldots, a_{i_k}\) where \(1 \leq i_1 < i_2 < \cdots < i_k \leq m\) and \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\). The goal is to maximize \(k\) after removing exactly one element from the original sequence.

inputFormat

The input consists of two lines:

• The first line contains an integer \(n\), representing the number of elements in the sequence.
• The second line contains \(n\) space-separated integers representing the elements of the sequence.

outputFormat

Output a single integer which is the maximum length of a strictly increasing subsequence of the sequence after removing exactly one element.

5
3 10 2 1 20

3