You are given an array aa consisting of nn integers.
You can remove at most one element from this array. Thus, the final length of the array is n?1n?1 or nn .
Your task is to calculate the maximum possible length of the strictly increasing contiguous subarray of the remaining array.
Recall that the contiguous subarray aa with indices from ll to rr is a[l…r]=al,al+1,…,ara[l…r]=al,al+1,…,ar . The subarray a[l…r]a[l…r] is called strictly increasing if al<al+1<?<aral<al+1<?<ar .
Input
The first line of the input contains one integer nn (2≤n≤2?1052≤n≤2?105 ) — the number of elements in aa .
The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109 ), where aiai is the ii -th element of aa .
Output
Print one integer — the maximum possible length of the strictly increasing contiguous subarray of the array aa 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 a3=5a3=5 . Then the resulting array will be equal to [1,2,3,4][1,2,3,4] and the length of its largest increasing subarray will be equal to 44 .
给你一个长度为 nn 的数组，你最多删除一个元素（也可以不删），求此条件限制下的最长上升子串长度。
f[i]表示以a[i]结尾并且包含a[i]的最长上升序列，
f[1] = 1;
for (int i = 2; i <= n; i ++) {if (a[i-1] < a[i]) f[i] = f[i-1]+1;else f[i] = 1;
}
g[i]表示以a[i]开头并且包含a[i]的最长上升序列，跟f[i]都是反着来
g[n] = 1;
for (int i = n-1; i >= 1; i --) {if (a[i] < a[i+1]) g[i] = g[i+1]+1;else g[i] = 1;
}
如果删除的点在不在最长上升序列里面则没有影响，只有一种情况有影响，那就是当a[i-1]>a[i+1]的时候而且此时f[i-1]+g[i+1]>最大值
则此时要更新最大值，这个想法真的是太妙了，我怎么想不出来。。。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#define pi 3.1415926
#define inf 0x3f3f3f3f
using namespace std;
const long long mod = 1e9 + 7;
#define ll long long
#define MAXN 1000005
/*struct node {int a, b;
}t[MAXN];
bool cmp(node x, node y) {return x.b < y.b;
}*/
int f[MAXN], g[MAXN], a[MAXN];
int main() {int n, ans = 0;cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];memset(f, 0, sizeof(f));memset(g, 0, sizeof(g));f[1] = 1;for (int i = 2; i <= n; i++) {if (a[i - 1] < a[i]) {f[i] = f[i - 1] + 1;}else {f[i] = 1;}}g[n] = 1;for (int i = n - 1; i >= 1; i--) {if (a[i] < a[i + 1]) {g[i] = g[i + 1] + 1;}else {g[i] = 1;}}for (int i = 1; i <= n; i++)ans = max(ans, f[i]);for (int i = 2; i < n; i++) {if (a[i - 1] < a[i + 1]) {ans = max(ans, g[i + 1] + f[i - 1]);}}cout << ans << endl;return 0;
}