Background

The famous "Data Deletion" is someone who loves traveling! On this day, he arrived in the mysterious country of ZYL.

When entering customs, he was asked a problem. If he answered correctly, he could successfully reach ZY, the capital of ZYL! As the mighty "Data Deletion", he actually spent $10^{-233}$ seconds to come up with a solution. It was really a bit hard! So he decided to use it to test you.

Problem Description

Given a sequence $a$ of length $n$, it is guaranteed that $a_i$ are positive integers. You need to choose a position $i$ and change $a_i$ to any integer. Maximize the length of the longest strictly increasing substring.

A strictly increasing substring means selecting several consecutive numbers from the sequence such that each later number is greater than the previous one (it cannot be equal to or smaller than the previous one).

For example, in the sequence $[1,4,2,3,5]$, the subsequence $[2,3,5]$ is a strictly increasing substring, while $[4,2,3]$ (not increasing) and $[1,2,3]$ (not consecutive) are not.

Input Format

The first line contains a positive integer $n$, representing the length of the sequence.

The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$, representing the sequence $a$.

Output Format

Output one line with one integer, representing the maximum possible length of the longest strictly increasing substring after the modification.

5
1 4 2 2 3

3

5
1 2 3 2 1

4

5
1 2 3 1 5

5

6
8 2 3 1 4 5

4

6
7 2 9 4 5 6

5

Hint

[Sample Explanation #1]

For sample #1, we can change the third position in the sequence $[1,4,2,2,3]$ to $5$, obtaining the new sequence $[1,4,5,2,3]$. The longest strictly increasing substring of this sequence is $[1,4,5]$, with length $3$.

It is easy to prove that there is no modification plan that makes the length of the longest strictly increasing substring greater than $3$.

[Sample Explanation #4]

For sample #4, we can change the third position in the sequence $[8,2,3,1,4,5]$ to $0$, obtaining the new sequence $[8,2,0,1,4,5]$. The longest strictly increasing substring of this sequence is $[0,1,4,5]$, with length $4$.

It is easy to prove that there is no modification plan that makes the length of the longest strictly increasing substring greater than $4$.

[Constraints]

For the first $20\%$ of the testdata, $n \le 5$, $a_i \le 5$.
For the first $40\%$ of the testdata, $n \le 10$, $a_i \le 10$.
For the first $70\%$ of the testdata, $n \le 300$.
For $100\%$ of the testdata, $1 \le n \le {10}^6$, $1 \le a_i \le {10}^9$.

Translated by ChatGPT 5