time limit per test2 seconds

memory limit per test256 megabytes

inputstandard input

outputstandard 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].

【题目链接】:http://codeforces.com/contest/602/problem/B

【题解】



用ST算法先搞出各个区间的最大、最小值

然后枚举区间的左端点、二分右端点.

判断依据就是最大值和最小值的差;

如果小于等于1则右端点可以再往右点。否则往左

一般用二分都能过吧。



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%I64d",&x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int MAXN = 1e5+100;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

int n;

int a[MAXN];

int ma[MAXN][18],mi[MAXN][20];

int pre2[20];

int need[MAXN];

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    rei(n);

    rep1(i,1,n)

        rei(a[i]),mi[i][0] = ma[i][0] = a[i];

    pre2[0] = 1;

    for (int i = 1; i <= 18; i++)

        pre2[i] = pre2[i - 1] << 1;

    need[1] = 0; need[2] = 1;

    int temp = 2;

    for (int i = 3; i <= n; i++)

        if (pre2[temp] == i)

            need[i] = need[i - 1] + 1, temp++;

        else

            need[i] = need[i - 1];

    for (int l = 1; pre2[l] <= n; l++)

        for (int i = 1;i <= n;i++)

            if (i + pre2[l] - 1 <= n)

            {

                ma[i][l] = max(ma[i][l - 1], ma[i + pre2[l - 1]][l - 1]);

                mi[i][l] = min(mi[i][l - 1], mi[i + pre2[l - 1]][l - 1]);

            }

    int ans = 0;

    rep1(i,1,n)

    {

        int l = i,r = n,tempr=l;

        while (l <= r)

        {

            int m = (l+r)>>1;

            int le = need[m-i+1];

            int mi1 = min(mi[i][le],mi[m-pre2[le]+1][le]);

            int ma1 = max(ma[i][le],ma[m-pre2[le]+1][le]);

            if (abs(mi1-ma1)<=1)

            {

                tempr = m;

                l = m+1;

            }

            else

                r = m-1;

        }

        if(tempr-i+1> ans)

            ans = tempr-i+1;

    }

    cout << ans << endl;

    return 0;

}

close