Codeforces-1000B B Light It Up

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 0 and turn power off at moment M. Moreover, the lamp allows you to set a program of switching its state (states are “lights on” and “lights off”). Unfortunately, some program is already installed into the lamp.

The lamp allows only good programs. Good program can be represented as a non-empty array aa, where 0<a1<a2<<a|a|<M.All aiai must be integers. Of course, preinstalled program is a good program.

The lamp follows program aa in next manner: at moment 0 turns power and light on. Then at moment aiai the lamp flips its state to opposite (if it was lit, it turns off, and vice versa). The state of the lamp flips instantly: for example, if you turn the light off at moment 1 and then do nothing, the total time when the lamp is lit will be 11. Finally, at moment 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 aa, so it still should be a good program after alteration. Insertion can be done between any pair of consecutive elements of a, or even at the begining or at the end of 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 xx till moment yy, then its lit for yxunits of time. Segments of time when the lamp is lit are summed up.

Input

First line contains two space separated integers nn and MM (1n1052M109) — the length of program aa and the moment when power turns off.

Second line contains nn space separated integers a1,a2,,an (0<a1<a2<<an<M) — initially installed program aa.

Output

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

Examples

Input

Copy
3 10
4 6 7

Output

Copy
8

Input

Copy
2 12
1 10

Output

Copy
9

Input

Copy
2 7
3 4

Output

Copy
6

Note

In the first example, one of possible optimal solutions is to insert value x=3 before a1a1, so program will be [3,4,6,7]and time of lamp being lit equals (30)+(64)+(107)=8(3−0)+(6−4)+(10−7)=8. Other possible solution is to insert x=5 in appropriate place.

In the second example, there is only one optimal solution: to insert x=2 between a1a1 and a2a2. Program will become [1,2,10], and answer will be (10)+(102)=9(1−0)+(10−2)=9.

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

题干好长!!

实际上是个贪心+前缀和的题目

代码先放上,解析明天再写

#include<iostream>
using namespace std;
const int maxn = 4e5 + 10;
typedef long long LL;
 int prog[maxn], n, m, ans[maxn];
 int main() {
  cin >> n >> m;
  prog[0] = 0;
  prog[n + 1] = m;//存储每个程序对应时刻,m时关闭
  for (int i = 1 ; i <= n ; i++) cin>>prog[i];
  int power = 1;
  ans[0] = 0;
  for (int i = 1 ; i <= n + 1 ; i++) {
    if(power)//如果这个时间段电源开着 
    {
      int temp=(prog[i] - prog[i - 1]);//表示时间差
        ans[i] = ans[i - 1]+ temp;
        power=!power;
    }
    else
    {
      ans[i] = ans[i - 1];//电源关着,结果也是等于上次状态
      power=!power;
    }
  }//ans是前缀和,记录时间
  int cnt = ans[n + 1];
  for (int i = 1 ; i <= n + 1 ; i++) {
    int temp=m - prog[i] - (ans[n + 1] - ans[i]);//总时间-未被影响的时间=变动时间
    cnt = max(cnt, ans[i] - 1 +temp);//插入值前的一个点ans[i]少了一个单位时间 加上新时间
  }
  cout<<cnt<<endl;
  return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

11 + 1 =