CF#333（Div2）B. Approximating a Constant Range（RMQ）

题目点我点我点我

B. Approximating a Constant Range time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

When Xellos was doing a practice course in university, he once had to measure the intensity of an effect that slowly approached equilibrium. A good way to determine the equilibrium intensity would be choosing a sufficiently large number of consecutive data points that seems as constant as possible and taking their average. Of course, with the usual sizes of data, it's nothing challenging — but why not make a similar programming contest problem while we're at it?

You're given a sequence of n data points a1, ..., an. There aren't any big jumps between consecutive data points — for each 1 ≤ i < n, it's guaranteed that |ai + 1 - ai| ≤ 1.

A range [l, r] of data points is said to be almost constant if the difference between the largest and the smallest value in that range is at most 1. Formally, let M be the maximum and m the minimum value of ai for l ≤ i ≤ r; the range [l, r] is almost constant if M - m ≤ 1.

Find the length of the longest almost constant range.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of data points.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 100 000).

Output

Print a single number — the maximum length of an almost constant range of the given sequence.

Examples input 5 1 2 3 3 2 output 4 input 11 5 4 5 5 6 7 8 8 8 7 6 output 5 Note

In the first sample, the longest almost constant range is [2, 5]; its length (the number of data points in it) is 4.

In the second sample, there are three almost constant ranges of length 4: [1, 4], [6, 9] and [7, 10]; the only almost constant range of the maximum length 5 is [6, 10].

题目大意：求序列最大的数与最小的数相差不超过1的区间最大长度。

解题思路：RMQ。

/* *********************************************** ┆ ┏┓　　　┏┓ ┆ ┆┏┛┻━━━┛┻┓ ┆ ┆┃　　　　　　　┃ ┆ ┆┃　　　━　　　┃ ┆ ┆┃　┳┛　┗┳　┃ ┆ ┆┃　　　　　　　┃ ┆ ┆┃　　　┻　　　┃ ┆ ┆┗━┓　马　┏━┛ ┆ ┆　　┃　勒　┃　　┆　　　　　　 ┆　　┃　戈　┗━━━┓ ┆ ┆　　┃　壁　　　　　┣┓┆ ┆　　┃　的草泥马　　┏┛┆ ┆　　┗┓┓┏━┳┓┏┛ ┆ ┆　　　┃┫┫　┃┫┫ ┆ ┆　　　┗┻┛　┗┻┛ ┆ ************************************************ */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> using namespace std; #define rep(i,a,b) for (int i=(a),_ed=(b);i<=_ed;i++) #define per(i,a,b) for (int i=(b),_ed=(a);i>=_ed;i--) #define pb push_back #define mp make_pair const int inf_int = 2e9; const long long inf_ll = 2e18; #define inf_add 0x3f3f3f3f #define mod 1000000007 #define LL long long #define ULL unsigned long long #define MS0(X) memset((X), 0, sizeof((X))) #define SelfType int SelfType Gcd(SelfType p,SelfType q){return q==0?p:Gcd(q,p%q);} SelfType Pow(SelfType p,SelfType q){SelfType ans=1;while(q){if(q&1)ans=ans*p;p=p*p;q>>=1;}return ans;} #define Sd(X) int (X); scanf("%d", &X) #define Sdd(X, Y) int X, Y; scanf("%d%d", &X, &Y) #define Sddd(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z) #define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin()) #define all(a) a.begin(), a.end() typedef pair<int, int> pii; typedef pair<long long, long long> pll; typedef vector<int> vi; typedef vector<long long> vll; inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra*fh;} //#pragma comment(linker, "/STACK:102400000,102400000") int a[100005]; int mx[100005][20],mi[100005][20]; void RMQ(int n) { for(int i=1;i<=n;i++) mx[i][0] = mi[i][0] = a[i]; for(int j=1;(1<<j)<=n;j++) { for(int i=1;i+(1<<j)-1<=n;i++) { mx[i][j] = max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]); mi[i][j] = min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]); } } } int query(int l,int r) { int k = 0; while((1<<(k+1))<(r-l+1))k++; int ans1 = max(mx[l][k],mx[r-(1<<k)+1][k]); int ans2 = min(mi[l][k],mi[r-(1<<k)+1][k]); return ans1-ans2; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); ios::sync_with_stdio(0); cin.tie(0); int n; n = read(); for(int i=1;i<=n;i++)a[i] = read(); RMQ(n); int p = 1; int ans = 0; for(int i=1;i<=n;i++) { while(p<=i && query(p,i)>1) { p++; } ans = max(ans,i-p+1); } printf("%d\n",ans); return 0; }