stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <vector>



using namespace std;



int main() {

	int n;

	cin >> n;

	vector<int> a(n);

	vector<int> b(n);

	vector<int> c(100005, 0);

	int maxi = 0;

	for (int i = 0; i < n; ++i) {

		cin >> a[i] >> b[i];

		maxi = max(maxi, b[i]);

		for (int j = a[i]; j <= b[i]; ++j) c[j]++;

	}



	int ans = 0;

	for (int i = maxi; i > 0; --i) {

		if (i - 1 <= c[i]) {

			ans = i - 1;

			break;

		}

	}

	cout << ans << endl;



	return 0;

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <algorithm>

#include <vector>



using namespace std;



int main() {

	int n;

	cin >> n;

	int a, b;

	vector<int> c(100005, 0);

	int maxi = 0;

	for (int i = 0; i < n; ++i) {

		cin >> a >> b;

		c[a]++;

		c[b + 1]--;

		maxi = max(maxi, b);

	}

	int ans = 0;

	for (int i = 1; i <= maxi; ++i) {

		c[i] += c[i - 1];

		if (c[i] >= i - 1) ans = i - 1;

	}

	cout << ans << endl;



	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int main(){

	int n,h[111111]={};

	cin>>n;

	int a,b;

	for(int i=0;i<n;i++){

		cin>>a>>b;

		h[a]++;

		h[b+1]--;

	}

	int ma=0;

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

		h[i]+=h[i-1];

		if(i<=h[i]+1)ma=max(ma,i-1);

	}

	cout<<ma<<endl;

	return 0;

}




// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

int im[100010]={};

int main(){

  int n;

  cin>>n;

  for(int i=0;i<n;i++){

    int a,b;

    cin>>a>>b;

    im[a]++;

    im[b+1]--;

  }

  int ans;

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

    im[i]+=im[i-1];

    if(im[i-1]>=i-2)ans=i-2;

  }

  cout<<ans<<endl;

  return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <queue>

#include <map>

#include <set>

#include <list>

#include <deque>

#include <string>

#include <algorithm>

#include <cmath>

#include <ctype.h>

using namespace std;

#define dump(a) cout << (a) << '\n';

typedef long long Int;

Int mod = 1e9+7;

Int MOD = 998244353;



int main() {

    ios::sync_with_stdio(false);

    Int n, m, d;

    cin >> n >> m >> d;

    double res = 0.0;

    for (Int i = 0; i < m - 1; i++) {

        res += (double)(n - d) * 2.0 / (double)(n * n);

    }

    if (d == 0) res /= 2.0;

    printf("%.12lf\n", res);

    return 0;  

}    

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



#define dump(x) cout << (x) << '\n'

#define Int int64_t

#define fi first

#define se second

#define all(x) (x).begin(), (x).end()



Int INF = 1e18;

int inf = 1e9;

Int mod = 1e9+7;



int main() {

    double n, m, d;

    cin >> n >> m >> d;

    double x = (n - d) * 2.0;

    if (d == 0) x = n;

    double a = (m - 1.0) / n;

    double b = x / n;

    printf("%.12lf\n", a * b);



    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>

//#include<boost/multiprecision/cpp_int.hpp>

//#include<boost/multiprecision/cpp_dec_float.hpp>

//namespace mp=boost::multiprecision;

//#define mulint mp::cpp_int

//#define mulfloat mp::cpp_dec_float_100

using namespace std;

struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

//constexpr int MOD=1000000007;

constexpr int MOD=998244353;

#define INF (1<<30)

#define LINF (lint)(1LL<<56)

#define endl "\n"

#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)

#define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)

#define Flag(x) (1<<(x))

#define Flagcount(x) __builtin_popcount(x)

#define pint pair<int,int>

#define pdouble pair<double,double>

#define plint pair<lint,lint>

#define fi first

#define se second

typedef long long lint;

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

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

const int MAX_N=2e5+5;



int main(void){

    lint n,m,d;

    cin >> n >> m >> d;

    cout << (d?2:1)*(n-d)*(m-1)/pow(n,2) << endl;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

int main(){float n,m,d;scanf("%f%f%f",&n,&m,&d);printf("%f",(d?2:1)*(n-d)*(m-1)/n/n);}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h> //Ithea Myse Valgulious

namespace chtholly{

typedef long long ll;

#define re0 register int

#define rec register char

#define rel register ll

#define gc getchar

#define pc putchar

#define p32 pc(' ')

#define pl puts("")

/*By Citrus*/

inline int read(){

  int x=0,f=1;char c=gc();

  for (;!isdigit(c);c=gc()) f^=c=='-';

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return f?x:-x;

  }

template <typename mitsuha>

inline bool read(mitsuha &x){

  x=0;int f=1;char c=gc();

  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';

  if (!~c) return 0;

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return x=f?x:-x,1;

  }

template <typename mitsuha>

inline int write(mitsuha x){

  if (!x) return 0&pc(48);

  if (x<0) x=-x,pc('-');

  int bit[20],i,p=0;

  for (;x;x/=10) bit[++p]=x%10;

  for (i=p;i;--i) pc(bit[i]+48);

  return 0;

  }

inline char fuhao(){

  char c=gc();

  for (;isspace(c);c=gc());

  return c;

  }

}using namespace chtholly;

using namespace std;

 

int main(){

ll n=read(),m=read(),d=read();

printf("%.10lf",1.0*((d!=0)+1)*(n-d)*(m-1)/(n*n));

}

// Optimized solution to the same problem (faster):
#include <cstdio>



int main() {

	int n, m, d;

	scanf("%d%d%d", &n, &m, &d);

	double t;

	if (d == 0) t = n;

	else t = (n - d) << 1;

	t *= m - 1;

	t /= n;

	t /= n;

	printf("%.10lf\n", t);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define int long long

const int inf = 1e18;

using namespace std;



template<typename tp> inline void read(tp &x) {

	x=0;char c=getchar();

	for(;c<'0'||c>'9';c=getchar());

	for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c=getchar());

}

const int N = 2e5 + 10 ; 

int x,y,z,n;

struct P {

	int a,b,c;

}p[N];

inline bool cmp(P a, P b) {

	return a.a-a.b<b.a-b.b;

}

int suma,sumb,sum,t1[N],t2[N],ans=0;

priority_queue<int,vector<int> , greater<int> > q;



main() {

	memset(t1,168,sizeof(t1));

	memset(t2,168,sizeof(t2));

	cin>>x>>y>>z;

	n=x+y+z;

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

		read(p[i].a);read(p[i].b);read(p[i].c);

		p[i].a-=p[i].c;

		p[i].b-=p[i].c;

		sum+=p[i].c;

	}

	sort(p+1,p+n+1,cmp);

	int ans=-inf;

	for(int k=1;k<=y;k++) q.push(p[k].b),sumb+=p[k].b,t1[k]=max(t1[k],sumb);

	for(int k=y+1;k<=n;k++) {

		int u=q.top();q.pop();

		sumb-=u;

		sumb+=max(u,p[k].b);

		t1[k]=max(t1[k],sumb);

		q.push(max(u,p[k].b));

	}

	while(!q.empty()) q.pop();

	for(int k=n;k>=n-x+1;k--) 

		q.push(p[k].a),suma+=p[k].a,t2[k]=max(t2[k],suma);

	for(int k=n-x;k>=1;k--) {

		int u=q.top();q.pop();

		suma-=u;

		suma+=max(u,p[k].a);

		t2[k]=max(t2[k],suma);

		q.push(max(u,p[k].a));

	}

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

//		printf("%d %d %d\n",p[i].a,p[i].b,p[i].c);

//	}

//	puts("____________");

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

//		printf("%d ",t1[i]);

//	}puts("____________");

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

//		printf("%d ",t2[i]);

//	}puts("____________");

	for(int k=y;k<=n-x;k++)

		ans=max(ans,t1[k]+t2[k+1]);

	cout<<ans+sum<<"\n";

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define N 100010

int n,X,Y,Z,a[N],b[N],c[N],id[N];

ll ans,tmp,s1[N],s2[N];

priority_queue<int,vector<int>,greater<int> >q;

inline char gc(){

    static char *S,*T,buf[1<<16];

    if(T==S){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;}

    return *S++;

}

inline int read(){

    int x=0,f=1;char ch=gc();

    while(ch<'0' || ch>'9'){if(ch=='-') f=-1;ch=gc();}

    while('0'<=ch && ch<='9') x=x*10+ch-'0',ch=gc();

    return x*f;

}

inline bool cmp(int x,int y){return a[x]-b[x]>a[y]-b[y];}

int main(){

	X=read();Y=read();Z=read();n=X+Y+Z;

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

		a[i]=read();b[i]=read();c[i]=read();

		id[i]=i;tmp+=b[i];

	}

	sort(id+1,id+n+1,cmp);

	for(int i=1;i<=X;++i){

		s1[i]=s1[i-1]+a[id[i]]-b[id[i]];

		q.push(a[id[i]]-c[id[i]]);

	}

	for(int i=X+1;i<=X+Z;++i){

		s1[i]=s1[i-1]+c[id[i]]-b[id[i]];

		if(a[id[i]]-c[id[i]]>q.top()){

			int x=q.top();q.pop();

			q.push(a[id[i]]-c[id[i]]);

			s1[i]+=-x+a[id[i]]-c[id[i]];

		}

	}

	while(!q.empty()) q.pop();

	for(int i=n;i>=n-Y+1;--i){

//		s2[i]=s2[i-1]+c[id[i]]-b[id[i]];

		q.push(b[id[i]]-c[id[i]]);

	}

	for(int i=n-Y;i>=X+1;--i){

		s2[i]=s2[i+1]+c[id[i]]-b[id[i]];

		if(b[id[i]]-c[id[i]]>q.top()){

			int x=q.top();q.pop();

			q.push(b[id[i]]-c[id[i]]);

			s2[i]+=-x+b[id[i]]-c[id[i]];

		}

	}

	for(int i=X;i<=X+Z;++i){

		ans=max(ans,tmp+s1[i]+s2[i+1]);

	}

	printf("%lld\n",ans);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;

const long long inf = 1e16;

long long pre[maxn], suf[maxn];

struct data {

  int a, b, c;

  data () {}

  bool operator < (data d) const {

    return b - a < d.b - d.a;

  }

} arr[maxn];

int t[maxn * 4];

long long sum[maxn * 4];

int rev[maxn];

int idx;



void add(int x, int c = 1, int b = 1, int e = idx) {

  if(b == e) {

    t[c] += 1;

    sum[c] += rev[b];

    return ;

  }

  int m = (b + e) >> 1;

  int l = c << 1;

  int r = l + 1;

  if(x <= m) add(x, l, b, m);

  else add(x, r, m + 1, e);

  t[c] = t[l] + t[r];

  sum[c] = sum[l] + sum[r];

}

long long get(int x, int c = 1, int b = 1, int e = idx) {

  if(b == e) {

    return 1LL * rev[b] * x;

  }

  int m = (b + e) >> 1;

  int l = c << 1;

  int r = l + 1;

  if(t[r] >= x) return get(x, r, m + 1, e);

  else return sum[r] + get(x - t[r], l, b, m);

}

int main() {

  ios_base :: sync_with_stdio (false); cin.tie(0);

  int X, Y, Z;

  cin >> X >> Y >> Z;

  int n = X + Y + Z;

  map <int, int> cmp;

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

    cin >> arr[i].a >> arr[i].b >> arr[i].c;

    cmp[arr[i].c - arr[i].a];

    cmp[arr[i].c - arr[i].b];

  }

  sort(arr + 1, arr + n + 1);

  for(auto &i : cmp) {

    i.second = ++idx;

    rev[idx] = i.first;

  }

  long long total = 0;

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

    int x = cmp[arr[i].c - arr[i].a];

    add(x);

    total += arr[i].a;

    if(i >= X) pre[i] = total + get(i - X);

    else pre[i] = -inf;

  }

  memset(t, 0, sizeof t);

  memset(sum, 0, sizeof sum);

  total = 0;

  for(int i = n; i >= 1; i--) {

    int x = cmp[arr[i].c - arr[i].b];

    add(x);

    total += arr[i].b;

    if(n - i + 1 >= Y) suf[i] = total + get(n - i + 1 - Y);

    else suf[i] = -inf;

  }

  long long ans = -inf;

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

    ans = max(ans, pre[i] + suf[i + 1]);

  }

  cout << ans << endl;

  return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



inline long long read()

{

	long long x=0,f=1,c=getchar();

	while(c<48) c=='-'&&(f=-1),c=getchar();

	while(c>47) x=x*10+c-'0',c=getchar();

	return x*f;

}



typedef long long ll;

const ll MAXN = 100005;

struct Node {ll a,b;} s[MAXN];

priority_queue<ll,vector<ll>,greater<ll> > q,ept;

ll lp[MAXN],rp[MAXN],ans;

ll n,x,y,z;



int main(int argc, char const *argv[])

{

	x=read(); y=read(); z=read(); n=x+y+z;

	for(ll i=1,k;i<=n;++i)

		ans+=(k=read()),s[i].a=read()-k,s[i].b=read()-k;

	sort(s+1,s+n+1,[](Node a,Node b)

	{return a.a-a.b>b.a-b.b;});

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

	{

		lp[i]=lp[i-1]+s[i].a; q.push(s[i].a);

		if(q.size()>y) lp[i]-=q.top(),q.pop();

	}

	for(ll i=(q=ept,n);i;--i)

	{

		rp[i]=rp[i+1]+s[i].b; q.push(s[i].b);

		if(q.size()>z) rp[i]-=q.top(),q.pop();

	}

	ll mx=-1000000000000000000ll;

	for(ll i=y;i<=n-z;++i)

		mx=max(mx,lp[i]+rp[i+1]);

	printf("%lld\n", ans+mx);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



struct Node{

	int p, q;

};



const int N = 1e5 + 10;



Node a[N];

long long sum[N];

priority_queue <int, vector <int>, greater <int> > pq;



bool cmp(const Node& x, const Node& y){

	return x.p - x.q < y.p - y.q;

}



int main(){

	int x, y, z, n, n1, n2, n3;

	long long ans, rec, maxx;

	scanf("%d %d %d",&x,&y,&z);

	n = x + y + z;

	ans = 0;

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

		scanf("%d %d %d",&n1,&n2,&n3);

		a[i].p = n1 - n3; a[i].q = n2 - n3;

		ans += n3;

	}

	sort(a + 1, a + n + 1, cmp);

	memset(sum, 0, sizeof(sum));

	rec = 0;

	for (int i = 1; i <= y; i++){

		pq.push(a[i].q);

		rec += a[i].q;

	}

	sum[y] = rec;

	for (int i = y + 1; i <= n - x; i++){

		if (a[i].q > pq.top()){

			rec += a[i].q - pq.top();

			pq.pop();

			pq.push(a[i].q);

		}

		sum[i] = rec;

	}

	while (!pq.empty()) pq.pop();

	rec = 0;

	for (int i = n; i >= n - x + 1; i--){

		pq.push(a[i].p);

		rec += a[i].p;

	}

	sum[n - x] += rec;

	for (int i = n - x; i > y; i--){

		if (a[i].p > pq.top()){

			rec += a[i].p - pq.top();

			pq.pop();

			pq.push(a[i].p);

		}

		sum[i - 1] += rec;

	}

	maxx = -1e18;

	for (int i = y; i <= n - x; i++) maxx = max(maxx, sum[i]);

	ans += maxx;

	printf("%lld\n", ans);

	return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <queue>

#include <algorithm>

#define N 201000

#define int long long

typedef long long ll;

template<typename T> inline void read(T &x) {

  x = 0; char c = getchar();

  while (!isdigit(c)) c = getchar();

  while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }

}

using namespace std;

const int inf = 1e18;

inline void MAX(ll &a, ll b) {

  if (b > a)  a = b;

}

int A, B, C, n;

ll ans = -inf, tmp;

struct node {

  int a, b;

}nd[N];

bool cmp(const node &a, const node &b) {

  return a.a - a.b > b.a - b.b;

}

ll f[N];

priority_queue<int, vector<int>, greater<int> > q;

inline void work() {

  ll res = 0;

  for (int i = 1; i <= A; ++i) {

    q.push(nd[i].a); res += nd[i].a;

  }

  f[A] = res;

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

    int a = nd[i].a;

    if (q.top() < a)  res -= q.top(), q.pop(), q.push(a), res += a;

    f[i] = res;

  }

  while (!q.empty())  q.pop();

  res = 0;

  for (int i = n; i > n - B; --i) q.push(nd[i].b), res += nd[i].b;

  MAX(ans, res + f[n - B]);

  for (int i = n - B; i > A; --i) {

    int b = nd[i].b;

    if (q.top() < b)  res -= q.top(), q.pop(), q.push(b), res += b;

    MAX(ans, res + f[i - 1]);

  }

  printf("%lld\n", ans + tmp);

}

signed main() {

  read(A), read(B), read(C);

  n = A + B + C;

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

    int a, b, c; read(a), read(b), read(c);

    tmp += c;

    nd[i] = (node){a - c, b - c};

  }

  sort(nd + 1, nd + 1 + n, cmp);

  work();

  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



int main (){

	long long a, b, v, w, t;

	scanf("%lld%lld%lld%lld%lld", &a, &v, &b, &w, &t);

	if(v * t >= ((a - b) > 0 ? (a - b) : (b - a)) + w * t){

		puts("YES");

		return 0;

	}

	puts("NO");

	return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>



typedef long long ll;



ll myabs(ll a) {

	return a > 0 ? a : -a;

}



int main() {

	ll a, b, v, w, t;

	scanf("%lld%lld%lld%lld%lld", &a, &v, &b, &w, &t);

	ll dif = myabs(a - b);

	if (dif > t * (v - w))

		puts("NO");

	else

		puts("YES");

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

#include<complex>

using namespace std;



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

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

#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



#define SZ(a) (int)a.size()

#define ALL(a) a.begin(), a.end()

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL)INF;



const int MAX = 1000 * 1000 + 47;



int n, e, t;

int X[MAX];

LL dp[MAX];



int main()

{

	//freopen("in.txt", "r", stdin);

	//freopen("out.txt", "w", stdout);

	ios::sync_with_stdio(false); cin.tie(0);

	int n, e, t;

	cin >> n >> e >> t;

	FOR(i, 0, n)

	{

		cin >> X[i];

	}



	FOR(i, 0, n + 1) dp[i] = INF;

	dp[0] = 0;

	int p = 0;

	LL minn = LINF;



	FOR(i, 1, n + 1)

	{

		while (2 * (X[i - 1] - X[p]) > t)

		{

			minn = min(dp[p] - 2 * X[p], minn);

			p++;

		}



		dp[i] = minn + 2 * X[i - 1];

		dp[i] = min(dp[i], dp[p] + t);

	}



	cout << dp[n] + e;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 100010

#define LL long long

LL dp[MAXN],a[MAXN],T,tmp=1000000000000000LL;

int n,m,t;

int main()

{

	scanf("%d%d%lld",&n,&m,&T);

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

		scanf("%lld",&a[i]);

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

	{

		while(T<=2*(a[i]-a[t+1]))

			tmp=min(tmp,dp[t]-2*a[t+1]),t++;

		dp[i]=min(tmp+2*a[i],dp[t]+T);

	}

	printf("%lld\n",dp[n]+m);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<set>

using namespace std;

long long dp[100010];

int x[100010];

int n,e;

long long t;

int st;

multiset<long long>s1,s2;

int main()

{

	scanf("%d%d%lld",&n,&e,&t);

	for(int i=1;i<=n;i++)scanf("%d",x+i);

	s2.insert(t);

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

	{

		while(st+1<i && 2*(x[i]-x[st+1])>=t)

		{

			s2.erase(s2.find(dp[st]-x[st]+t));

			s1.insert(dp[st]-x[st]-2LL*x[st+1]);

			st++;

		}

		dp[i]=4e18;

		if(s1.size())dp[i]=min(dp[i],(*s1.begin())+3LL*x[i]);

		if(s2.size())dp[i]=min(dp[i],x[i]+(*s2.begin())),

		s2.insert(dp[i]-x[i]+t);

	}

	printf("%lld",dp[n]+e-x[n]);

	return 0;

} 

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 100010

#define LL long long

LL dp[MAXN],a[MAXN],T,tmp=1000000000000000LL;

int n,m,t;

int main()

{

	scanf("%d%d%lld",&n,&m,&T);

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

		scanf("%lld",&a[i]);

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

	{

		while(T<=2*(a[i]-a[t+1]))

			tmp=min(tmp,dp[t]-2*a[t+1]),t++;

		dp[i]=min(tmp+2*a[i],dp[t]+T);

	}

	printf("%lld\n",dp[n]+m);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>



using namespace std;

using namespace __gnu_pbds;



#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define fbo find_by_order

#define ook order_of_key



typedef long long ll;

typedef pair<int,int> ii;

typedef vector<int> vi;

typedef long double ld; 

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

typedef set<int>::iterator sit;

typedef map<int,int>::iterator mit;

typedef vector<int>::iterator vit;



ll x[111111];

ll dp[111111];

int main()

{

	ios_base::sync_with_stdio(0); cin.tie(0);

	ll lmin=ll(1e18); 

	deque<pair<ll,ll> > rmin;

	int n; cin>>n; ll e,t; cin>>e>>t;

	x[0]=0;

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

	{

		cin>>x[i];

	}

	int ptr=1;

	rmin.pb(mp(dp[0]-x[0]+t,1));

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

	{

		while(ptr<=i&&x[i]>=t/2+x[ptr]+1) //this means that we need to remove ptr from the "T - 2(x_i - x_{j+1})" is large part

		{

			if(!rmin.empty()&&rmin.front().se==ptr) rmin.pop_front();

			lmin = min(lmin, dp[ptr-1]-2*x[ptr]-x[ptr-1]);

			ptr++;

		}

		ll best=lmin;

		if(!rmin.empty()) best=min(best,-2*x[i]+rmin.front().fi);

		dp[i]=best+3LL*x[i];

		ll cost = dp[i]-x[i]+t;

		while(!rmin.empty()&&rmin.back().fi>=cost) rmin.pop_back();

		rmin.pb(mp(cost,i+1));

	}

	cout<<dp[n]+e-x[n];

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 100010

#define LL long long

LL dp[MAXN],a[MAXN],T,tmp=1000000000000000LL;

int n,m,t;

int main()

{

	scanf("%d%d%lld",&n,&m,&T);

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

		scanf("%lld",&a[i]);

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

	{

		while(T<=2*(a[i]-a[t+1]))

			tmp=min(tmp,dp[t]-2*a[t+1]),t++;

		dp[i]=min(tmp+2*a[i],dp[t]+T);

	}

	printf("%lld\n",dp[n]+m);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<vector>

#include<queue>

#include<set>

#include<map>

#define ll long long

#define inf 1e9

#define eps 1e-10

#define mod 9901

#define mkp make_pair

using namespace std;

int i,j,k,m,s,t,n,ans1,ans2,n1,nn,m1,mx;

int read()

{

	int x=0,f=1;char ch=getchar();

	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}

	while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

int kabs(int a)

{

   if (a<0) return -a;

   return a; 

}

void add(int &x,int y)

{

   x+=y;

   if (x>=mod) x-=mod;

}

void dec(int &x,int y)

{

	x-=y;

	if (x<0) x+=mod;

}

int a[101000];

ll f[101000];

int main()

{

	int e;

	scanf("%d%d%d",&n,&e,&t);

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

		scanf("%d",&a[i]);

	j=0;

	ll s=1e18;

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

		f[i]=1e18;

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

	{

		while (2*(a[i]-a[j+1])>=t)

			s=min(s,f[j]-2ll*a[j+1]),j++;

		f[i]=min(f[j]+t,2ll*a[i]+s);

	}

	printf("%lld\n",f[n]+e);

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 100010

#define LL long long

LL dp[MAXN],a[MAXN],T,tmp=1000000000000000LL;

int n,m,t;

int main()

{

	scanf("%d%d%lld",&n,&m,&T);

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

		scanf("%lld",&a[i]);

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

	{

		while(T<=2*(a[i]-a[t+1]))

			tmp=min(tmp,dp[t]-2*a[t+1]),t++;

		dp[i]=min(tmp+2*a[i],dp[t]+T);

	}

	printf("%lld\n",dp[n]+m);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int MAXN=1e5+5;

const ll inf=(1ll<<63-1);

ll a[MAXN];

ll dp[MAXN];

int main()

{

 

    ll n,e,t;

    cin>>n>>e>>t;

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

    {

        cin>>a[i];

    }

    memset(dp,(ll)0x3f3f3f3f,sizeof(dp));

    dp[0]=0;

    ll mn=inf;

    for(int i=1,now=0;i<=n;i++){

        while(t<=2*(a[i]-a[now+1]))

        {

            mn=min(mn,dp[now]-2*a[now+1]);

            now++;

        }

        dp[i]=dp[now]+t;

        dp[i]=min(dp[i],mn+2*a[i]);

 

    }

    cout<<e+dp[n]<<endl;

    return 0;

 

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll n,S,T,i,la,now,f[200001],a[200001];

int main(){

	scanf("%lld%lld%lld",&n,&S,&T);

	for(i=1;i<=n;i++)scanf("%lld",&a[i]);

	la=0;now=1e9;

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

		while(la<i&&2*(a[i]-a[la+1])>T){

			now=min(now,f[la]-2*a[la+1]);

			la++;

		}

		f[i]=min(2*a[i]+now,f[la]+T);

	}

	f[n]+=a[n]+abs(a[n]-S);

	printf("%lld",f[n]);

}

/*

最后肯定被分成一段段 

*/

// Fastest known solution for this problem: