You are given an array $a$ consisting of $n$ integers.

You can remove at most one element from this array. Thus, the final length of the array is $n-1$ or $n$.

Your task is to calculate the maximum possible length of the strictly increasing contiguous subarray of the remaining array.

Recall that the contiguous subarray $a$ with indices from $l$ to $r$ is $a[l \dots r] = a_l, a_{l + 1}, \dots, a_r$. The subarray $a[l \dots r]$ is called strictly increasing if $a_l < a_{l+1} < \dots < a_r$.


-----Input-----

The first line of the input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of elements in $a$.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the $i$-th element of $a$.


-----Output-----

Print one integer — the maximum possible length of the strictly increasing contiguous subarray of the array $a$ after removing at most one element.


-----Examples-----
Input
5
1 2 5 3 4

Output
4

Input
2
1 2

Output
2

Input
7
6 5 4 3 2 4 3

Output
2



-----Note-----

In the first example, you can delete $a_3=5$. Then the resulting array will be equal to $[1, 2, 3, 4]$ and the length of its largest increasing subarray will be equal to $4$.

Difficulty: introductory

Starter code:

Solutions:
n = int(input())
mass = list(map(int, input().split()))
left = [1] * n
right = [1] * n
for i in range(1, n):
    if mass[i] > mass[i - 1]:
        left[i] = left[i - 1] + 1
for i in range(n - 2, -1, -1):
    if mass[i] < mass[i + 1]:
        right[i] = right[i + 1] + 1
mx = 1
for i in range(n):
    if i == 0:
        mx = max(right[0], mx)
    elif i == n - 1:
        mx = max(mx, left[n - 1])
    elif mass[i + 1] > mass[i - 1]:
        mx = max(mx, left[i - 1] + right[i + 1])
    mx = max(mx, left[i])
    mx = max(mx, right[i])
print(mx)



def main():
    buf = input()
    n = int(buf)
    buf = input()
    buflist = buf.split()
    a = list(map(int, buflist))

    sublen_inc = []
    sublen_dec = []
    for i in range(n):
        sublen_inc.append(None)
        sublen_dec.append(None)
    c = 1
    sublen_inc[0] = c
    for i in range(1, n):
        if a[i-1] < a[i]:
            c += 1
        else:
            c = 1
        sublen_inc[i] = c
    c = 1
    sublen_dec[n-1] = c
    for i in range(n-2, -1, -1):
        if a[i] < a[i+1]:
            c += 1
        else:
            c = 1
        sublen_dec[i] = c

    best = max(sublen_inc)
    for i in range(1, n-1):
        if a[i-1] < a[i+1]:
            new_sublen = sublen_inc[i-1] + sublen_dec[i+1]
            if new_sublen > best:
                best = new_sublen

    print(best)

def __starting_point():
    main()

__starting_point()

n = int(input())
a = [-1] + list(map(int,input().split()))

cur = 0
l = [0] * n
m = [0] * n

for i in range(1, n + 1):
    if a[i] > a[i - 1]:
        cur += 1
    else:
        cur = 1
    l[i - 1] = cur

cur = n - 1
num = l[cur]
while cur >= 0:
    m[cur] = num
    if l[cur] == 1:
        num = l[cur - 1]
    cur -= 1

res = max(m)
a = a[1:]

for i in range(1, n - 1):
    if l[i - 1] + 2 != l[i + 1] and a[i - 1] < a[i + 1]:
        res = max(res, m[i - 1] + m[i + 1] - 1)

print(res)

# print(l)
# print(m)


n=int(input())
l=list(map(int,input().split()))
end=[1]
for i in range(1,n):
	if l[i]>l[i-1]:
		end.append(end[-1]+1)
	else:
		end.append(1)
strt=[1]*n
for i in range(n-2,-1,-1):
	if l[i]<l[i+1]:
		strt[i]=strt[i+1]+1
	else:
		strt[i]=1
ans=max(max(end),max(strt))
for i in range(1,n-1):
	if l[i+1]>l[i-1]:
		ans=max(ans,end[i-1]+strt[i+1])
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
a += [0]

dp = [0] * (n + 5)
i = n-2
dp[n-1] = 1
while (i >= 0):
    if (a[i] < a[i+1]):
        dp[i] = dp[i+1] + 1
    else:
        dp[i] = 1
    i -= 1

temp = 1
ans = 1
for i in range(1, n):
    if a[i+1] > a[i-1]:
        ans = max(ans, temp + dp[i + 1])
    if a[i] > a[i-1]:
        temp += 1
    else:
        temp = 1
    ans = max(ans, temp)

print(ans)

import sys
input = sys.stdin.readline

n=int(input())
A=list(map(int,input().split()))

ANS=[0]*n
count=1
ANS[0]=1

ANS2=[0]*n
ucount=0

for i in range(1,n):
    if A[i]>A[i-1]:
        count+=1
        ANS[i]=count

        if ucount>0:
            ucount+=1
            ANS2[i]=ucount
    else:
        count=1
        ANS[i]=count
        ucount=0

    if i>=2 and A[i-2]<A[i]:
        ucount=max(ucount,ANS[i-2]+1)
        ANS2[i]=ucount

print(max((max(ANS)),max(ANS2)))
    


n = int(input())
a = list(map(int, input().split()))
dp = [1 for i in range(n)]
dpStart = [1 for i in range(n)]
for i in range(1, n):
    if a[i] > a[i - 1]:
        dp[i] = dp[i - 1] + 1
for i in range(n - 2, -1, -1):
    if a[i] < a[i + 1]:
        dpStart[i] = dpStart[i + 1] + 1
m = max(dp)
ans = m
for i in range(1, n - 1):
    # print(ans)
    if a[i - 1] < a[i + 1]:
        ans = max(ans, dp[i - 1] + dpStart[i + 1])

print(ans)