Longest Increasing Prefix After Removing at Most One Element

You are given a sequence of integers and your task is to determine the length of the longest increasing prefix possible after removing at most one element from the sequence. Formally, you are allowed to remove at most one element to potentially extend the prefix in which the elements are in a strictly increasing order.

Let \(a_1, a_2, \dots, a_n\) be the given sequence. You need to find the maximum \(k\) such that, after removing at most one element, the prefix of the remaining sequence \(a'_1, a'_2, \dots, a'_k\) satisfies \(a'_1 < a'_2 < \cdots < a'_k\).

If the sequence is already strictly increasing from the start, no removal is needed. Otherwise, you may remove one element to try to restore the increasing order for a longer prefix.

inputFormat

The input is given via standard input and consists of two lines. The first line contains an integer \(n\) (the length of the sequence). The second line contains \(n\) space-separated integers representing the sequence.

For example:

6
10 20 30 50 60 70

outputFormat

Output a single integer on standard output: the length of the longest strictly increasing prefix obtainable after removing at most one element.

6
10 20 30 50 60 70

6