Roses in a shop
/

## Algorithms, Dynamic Programming

Problem
Editorial
Analytics

There are $n$ roses in a shop. Each rose is assigned an ID. These roses are arranged in order $1,\ 2,\ 3,\ ... ,\ n$. Each rose has a smell factor denoted as $smell[i]$ ($1 \le i \le n$). You want to buy roses from this shop under the condition that you can buy roses in a segment. In other words, you can purchase roses from $l$ to $r$ ($1 \le l \le r \le n$). You can remove at most one rose from this segment of roses. Thus, the final length of roses is $n-1$ or $n$.

Your task is to calculate the maximum possible length of the strictly-increasing contiguous subarray of the smell factors of these roses.

Note: A contiguous subarray $a$ with indices from $l$ to $r$ is $a[l,\ ...,\ r]=a[l],\ a[l+1] ,\ ...,\ a[r]$. The subarray $a[l,\ ...,\ r]$ is strictly increasing if $a[l]<a[l+1]<\ ...\ <a[r]$.

Input format

• The first line contains a single integer $n$ denoting the number of roses that are available in the shop.
• The second line contains $n$ space-separated integers $smell[1],\ smell[2],\ ... ,\ smell[n]$.

Output format

Print one integer denoting the maximum possible length of the strictly-increasing contiguous subarray of the smell factor after removing at most one element.

Constraints

$2 \le n \le 2\times 10^5 \\ 1 \le smell[i] \le 10^9$

SAMPLE INPUT
5
1 2 5 3 4

SAMPLE OUTPUT
4

Explanation

In this case, you can get the maximum length by removing the 3rd element.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...