Educational Codeforces Round 46 (Rated for Div. 2)

链接http://codeforces.com/contest/1000

Recently, you bought a brand new smart lamp with programming features. At first, you set up a schedule to the lamp. Every day it will turn power on at moment

The lamp allows only good programs. Good program can be represented as a non-empty array ai must be integers. Of course, preinstalled program is a good program.

The lamp follows program M the lamp is turning its power off regardless of its state.

Since you are not among those people who read instructions, and you don't understand the language it's written in, you realize (after some testing) the only possible way to alter the preinstalled program. You can insert at most one element into the program a.

Find such a way to alter the program that the total time when the lamp is lit is maximum possible. Maybe you should leave program untouched. If the lamp is lit from y−x units of time. Segments of time when the lamp is lit are summed up.

Input

First line contains two space separated integers a and the moment when power turns off.

Second line contains a.

Output

Print the only integer — maximum possible total time when the lamp is lit.

Examples

input

Copy

3 10
4 6 7

output

Copy

input

Copy

2 12
1 10

output

Copy

input

Copy

2 7
3 4

output

Copy

Note

In the first example, one of possible optimal solutions is to insert value x=5 in appropriate place.

In the second example, there is only one optimal solution: to insert (1−0)+(10−2)=9.

In the third example, optimal answer is to leave program untouched, so answer will be (3−0)+(7−4)=6.

Recently, you bought a brand new smart lamp with programming features. At first, you set up a schedule to the lamp. Every day it will turn power on at moment

The lamp allows only good programs. Good program can be represented as a non-empty array ai must be integers. Of course, preinstalled program is a good program.

The lamp follows program M the lamp is turning its power off regardless of its state.

Input

First line contains two space separated integers a and the moment when power turns off.

Second line contains a.

Output

Print the only integer — maximum possible total time when the lamp is lit.

Examples

input

Copy

3 10
4 6 7

output

Copy

input

Copy

2 12
1 10

output

Copy

input

Copy

2 7
3 4

output

Copy

Note

In the first example, one of possible optimal solutions is to insert value x=5 in appropriate place.

In the second example, there is only one optimal solution: to insert (1−0)+(10−2)=9.

In the third example, optimal answer is to leave program untouched, so answer will be (3−0)+(7−4)=6.

$(3 - 0) + (7 - 4) = 6$

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#define DEBUG(x) cout<<#x<<" = "<<x<<endl
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
int n,M;
int prog[MAXN];
ll litTime[MAXN];
ll OnLitTimeToEnd[MAXN];
ll OffLitTimeToEnd[MAXN];
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&M);
    prog[0]=0,prog[n+1]=M;
    litTime[0]=0;
    for(int i=1;i<=n+1 ;i++ ){
        if(i<n+1)
            scanf("%d",&prog[i]);
        if(i%2)litTime[i]=litTime[i-1]+prog[i]-prog[i-1];
        else litTime[i]=litTime[i-1];
    }
    OffLitTimeToEnd[n+1]=0;
    OnLitTimeToEnd[n+1]=0;
    for(int i=n;i>=0 ;i-- ){
        OnLitTimeToEnd[i]=OffLitTimeToEnd[i+1]+prog[i+1]-prog[i];
///踩了一个坑     OnLitTimeToEnd[i]=OffLitTimeToEnd[i-1]+prog[i+1]-prog[i];
        OffLitTimeToEnd[i]=OnLitTimeToEnd[i+1];
    }
    int ans=litTime[n+1];
    for(int i=1;i<=n+1 ;i++ ){
        int t;
        if(i%2){///关
            t=prog[i]-1-prog[i-1]+litTime[i-1]+OnLitTimeToEnd[i];
        }
        else {///开
            t=prog[i]-(prog[i-1]+1)+litTime[i-1]+OffLitTimeToEnd[i];
        }
        ans=max(ans,t);
    }
    printf("%d
",ans);
}

View Code

You are given n segments on a coordinate line; each endpoint of every segment has integer coordinates. Some segments can degenerate to points. Segments can intersect with each other, be nested in each other or even coincide.

Your task is the following: for every li≤x≤ri.

Input

The first line of the input contains one integer 1≤n≤2⋅105) — the number of segments.

The next i-th segment.

Output

Print i.

Examples

input

Copy

output

Copy

6 2 1

input

Copy

output

Copy

5 2 0

Note

The picture describing the first example:

$Educational Codeforces Round 46 (Rated for Div. 2)$

Points with coordinates [3] is covered by three segments.

The picture describing the second example:

$Educational Codeforces Round 46 (Rated for Div. 2)$

Points [2,3] are covered by two segments and there are no points covered by three segments.

$[1, 4, 5, 6, 7]$

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#define DEBUG(x) cout<<#x<<" = "<<x<<endl
typedef long long ll;
using namespace std;
const int MAXN=4e5+10;
struct Point{
    ll pos;
    ll delta;
    Point(){}
    Point(ll p,ll d):pos(p),delta(d){}
    bool operator<(const Point &p)const
    {
        if(pos!=p.pos)return pos<p.pos;
        return delta>p.delta;
    }
};
int N;
Point points[MAXN];
ll ans[MAXN];
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d",&N);
    for(int i=0;i<2*N ;i++ ){
        scanf("%lld",&points[i].pos);
        if(i%2==0)points[i].delta=1;
        else {
                points[i].delta=-1;
                ///需要包括右端点
                points[i].pos++;
        }
    }
    sort(points,points+2*N);
    int curCov=0;
    for(int i=0;i<2*N-1 ;i++ ){
        curCov+=points[i].delta;
        ans[curCov]+=points[i+1].pos-points[i].pos;
    }
    for(int i=1;i<=N ;i++ ){
        printf("%lld",ans[i]);
        if(i==N)printf("
");
        else printf(" ");
    }
}

View Code

Educational Codeforces Round 46 (Rated for Div. 2)

相关推荐