stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;



const int N = 1e5 + 10;

const long long inf = 1e17 + 7;



int n, E, T, d[N];



struct node {

	int l, r;

	long long max;	

};

	

struct segTree {

	node h[N << 2];

	int p[N];

	

	void build(int x, int l, int r) {

		h[x].l = l; h[x].r = r; h[x].max = -inf;

		if (l == r) {

			p[l] = x;

			return;

		}

		int m = (l + r) / 2, L = x * 2, R = L + 1;

		build(L, l, m); build(R, m + 1, r);

	}

	void init(int n) {

		build(1, 1, n);

	}

	

	void modify(int x, int l, int r, long long k) {

		if (l > r) return;

		if (h[x].l == l && h[x].r == r) {

			h[x].max = max(h[x].max, k);

			return;	

		}

		

		int m = (h[x].l + h[x].r) / 2;

		int L = x * 2, R = L + 1;

		h[L].max = max(h[L].max, h[x].max);

		h[R].max = max(h[R].max, h[x].max);

		

		if (r <= m) modify(L, l, r, k);

		else if (l >= m + 1) modify(R, l, r, k);

		else {

			modify(L, l, m, k);

			modify(R, m + 1, r, k);	

		}

	}

	

	long long getmax(int id) {

		int x = p[id];

		long long res = -inf;

		while (x) {

			res = max(res, h[x].max);

			x /= 2;

		}

		return res;

	}

} a, b;



int Find(int l, int r, long long k) {

	while (l < r) {

		int m = (l + r) / 2;

		if (m == n + 1 || 2 * d[m] >= k) r = m;

		else l = m + 1;

	}

	return l;

}



int main() {

	scanf("%d%d%d", &n, &E, &T);

	d[0] = 0;

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

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

	a.init(n); b.init(n);

	long long ans = 0;

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

		int t;

		t = Find(i, n + 1, 1LL * T + 2 * d[i]);

		//printf("...%d %d\n", i, t);

		a.modify(1, i, t - 1, ans - 2 * d[i - 1] - T);

		b.modify(1, t, n, ans + 2 * d[i] - 2 * d[i - 1]);

		ans = max(a.getmax(i) + 2 * d[i], b.getmax(i));

		//printf("%d %lld\n", i, ans);

	}

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

	printf("%lld\n", -ans + 2 * d[n] + E);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.160845299241055x):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

    scanf("%d%d%d", &n, &E, &T);

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

        f[i] = min(f[pos] + T, f[i]);

    }

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

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<queue>

using namespace std;

long long f[101010];

long long x[101010];

long long E,T;

long long calc(int i,int j)

{

	return max(f[j-1]+T,f[j-1]+2*x[i]-2*x[j]);

}

priority_queue<long long> Q;

int main()

{

	int n;

	cin>>n>>E>>T;

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

		cin>>x[i];

	f[1]=T;

	int now=0;

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

	{

		f[i]=f[i-1]+T;

		int l=1,r=i-1;

		while(r>l)

		{

			int m=(l+r)/2;

			if(T-2*x[i]+2*x[m]>=0)

				r=m;

			else

				l=m+1;

		}

		f[i]=min(f[i],max(f[l-1]+T,f[l-1]+2*x[i]-2*x[l]));

		if(l>1)

		{

			while(now<l-1)

			{

				now++;

				Q.push(2*x[now]-f[now-1]);

			}

			f[i]=min(f[i],2*x[i]-Q.top());

		}

	}

	cout<<f[n]+E<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.234773471515727x):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

    scanf("%d%d%d", &n, &E, &T);

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

        f[i] = min(f[pos] + T, f[i]);

    }

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

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define N 111111

#define M 444444

#define LL long long

using namespace std;

int n,i,k,j,a[N];LL f[N],V1[M],V2[M],E,T;

void ins(int k,int l,int r,int x,LL z1,LL z2){

	if(l==r){V1[k]=z1;V2[k]=z2;return;}

	int md=l+r>>1;

	if(x<=md)ins(k<<1,l,md,x,z1,z2);else ins(k<<1|1,md+1,r,x,z1,z2);

	V1[k]=min(V1[k<<1],V1[k<<1|1]);

	V2[k]=min(V2[k<<1],V2[k<<1|1]);

}

LL qu1(int k,int l,int r,int x,int y){

	if(x>y)return 1e18;

	if(x<=l&&r<=y)return V1[k];

	int md=l+r>>1;

	if(y<=md)return qu1(k<<1,l,md,x,y);

	if(x>md)return qu1(k<<1|1,md+1,r,x,y);

	return min(qu1(k<<1,l,md,x,y),qu1(k<<1|1,md+1,r,x,y));

}

LL qu2(int k,int l,int r,int x,int y){

	if(x>y)return 1e18;

	if(x<=l&&r<=y)return V2[k];

	int md=l+r>>1;

	if(y<=md)return qu2(k<<1,l,md,x,y);

	if(x>md)return qu2(k<<1|1,md+1,r,x,y);

	return min(qu2(k<<1,l,md,x,y),qu2(k<<1|1,md+1,r,x,y));

}

int main(){

	for(i=0;i<M;i++)V1[i]=V2[i]=1e18;

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

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

	for(i=0,k=0;i<=n;i++){

		f[i]=1e18;

		for(;(a[i]-a[k+1])*2>T&&k<i;k++);

		//f[i]=f[k]+max(a[i]-a[k+1]+a[i]-a[k+1],T)+a[i]-a[k];

		//j<=k a[i]-a[j+1*2>T

		//f[i]=qu2(1,0,0,k)

	//	printf("%d %d\n",(a[i]-a[k+1])*2,T);

		if(i==0)f[i]=0;else 

		f[i]=min(qu1(1,0,n,k,i-1)+T+a[i],qu2(1,0,n,0,k-1)+1ll*a[i]*3);

		//printf("%lld %lld\n",qu1(1,0,n,k,i-1)+T+a[i],qu2(1,0,n,0,k-1)+1ll*a[i]*3);

		//printf("%d %d %lld\n",i,k,f[i]);

	//	printf("%lld %lld %d\n",qu1(1,0,n,k,i-1),qu2(1,0,n,0,k-1),T+a[i]);

		//puts("-----------------------");

			//f[i]=min(f[i],f[j]+a[i]-a[j]+max((a[i]-a[j+1])*2,T));

		

		ins(1,0,n,i,f[i]-a[i],f[i]-a[i]-a[i+1]*2);

	}

	printf("%lld\n",f[n]+E-a[n]);

}

// Faster C++ solution for the same problem (measured speedup: 44.46444219296457x):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

    scanf("%d%d%d", &n, &E, &T);

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

        f[i] = min(f[pos] + T, f[i]);

    }

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

    return 0;

}
// Slower C++ solution:
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <iostream>

#include <queue>

using namespace std;



int n, e, t;

int x[101010];

long long f[101010];



long long calc(int a, int b)

{

	return max(f[b - 1] + t, f[b - 1] + 2 * x[a] - 2 * x[b]);

}



priority_queue<long long> q;



int main()

{

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

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

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

	f[1] = t;

	int now = 0;

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

	{

		f[i] = f[i - 1] + t;

		int l = 1;

		int r = i - 1, mid, key = i;

		while(l <= r)

		{

			mid = l + r;

			mid>>=1;

			if(t + 2 * x[mid] - 2 * x[i] >= 0)

			{

				r = mid - 1;

				key = mid;

			}

			else

				l = mid + 1;

		}

		f[i] = min(f[i], max(f[key - 1] + 2 * x[i] - 2 * x[key], f[key - 1] + t));

		if(key > 1)

		{

			while(now < key - 1)

			{

				++now;

				q.push(2 * x[now] - f[now - 1]);

			}

			f[i] = min(f[i], 2 * x[i] - q.top());

		}

	}

	

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

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



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.219370483517035x):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

    scanf("%d%d%d", &n, &E, &T);

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

        f[i] = min(f[pos] + T, f[i]);

    }

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

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef long double DD;

const int inf = 1e9;

const int mo= 1e9+7;

const int N = 101010;

int n;

LL T, E, f[N], p[N];



struct sta{

	LL f,d;

	sta(){}

	sta(LL x, LL y){

		f = x;

		d = y;

	}

	friend bool operator <(sta a, sta b){

		if(a.f == b.f)

			return a.d<b.d;

		else 

			return a.f < b.f;

	}

};

set<sta> s1,s2;



int main(){

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

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

		scanf("%lld", p + i);

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

	s1.insert(sta(T, p[1]));

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

		while(!s1.empty() && (p[i] - (*s1.begin()).d) * 2 > T){

			sta t = *s1.begin();

			s1.erase(s1.begin());

			s2.insert( sta(t.f - T - t.d * 2, t.d) );

		}

		f[i]=1ll << 62;

		if(!s2.empty())

			f[i]=(*s2.begin()).f + p[i] * 3;

		if(!s1.empty())

			f[i] = min(f[i], (*s1.begin()).f + p[i]);

		s1.insert(sta(f[i] - p[i] + T, p[i + 1]));

	}

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

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

	printf("%lld\n", f[n] + abs(E - p[n]));

	return 0;

}






// Faster C++ solution for the same problem (measured speedup: 5.217286985990796x):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

    scanf("%d%d%d", &n, &E, &T);

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

        f[i] = min(f[pos] + T, f[i]);

    }

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

    return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <algorithm>

using namespace std;

inline int read()

{

	int res, ok = 1;

	char ch;

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

	if (ch == '-')

	ok = -1;

	res = ch - '0';

	for (ch = getchar(); ch >= '0' && ch <= '9'; ch = getchar())

	res = res * 10 + ch - '0';

	return res * ok;

}

int n, t, e, a[100005], last;

long long ans[100005], minn = 1LL << 60;

int main()

{

	n = read();

	e = read();

	t = read();

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

	a[i] = read();

	ans[0] = 0;

	ans[1] = t;

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

	{

		while (2LL * (a[i] - a[last + 1]) > t)

		{

			long long now = ans[last] - 2LL * a[last + 1];

			minn = min (minn, now);

			last++;

		}

		ans[i] = ans[i - 1] + t;

		if (last > 0)

		ans[i] = min (ans[i], minn + 2LL * a[i]);

		ans[i] = min (ans[i], ans[last] + t);

	}

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

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.1388597808491525x):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

    scanf("%d%d%d", &n, &E, &T);

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

        f[i] = min(f[pos] + T, f[i]);

    }

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

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;



#define lowbit(a) (a&-a)

typedef long long ll;

const int maxn = 100010; const ll inf = 1LL<<60;

int N,T,E,X[maxn]; ll tree1[4*maxn],tree2[4*maxn],f[maxn];



inline int gi()

{

	char ch; int ret = 0,f = 1;

	do ch = getchar(); while (!(ch >= '0'&&ch <= '9')&&ch != '-');

	if (ch == '-') f = -1,ch = getchar();

	do ret = ret*10+ch-'0',ch = getchar(); while (ch >= '0'&&ch <= '9');

	return ret*f;

}



inline void build(int now,int l,int r)

{

	tree1[now] = tree2[now] = inf;

	if (l == r) return; int mid = (l+r) >> 1;

	build(now<<1,l,mid); build(now<<1|1,mid+1,r);

}



inline void modify(ll *tree,int now,int l,int r,int pos,ll key)

{

	if (l == r) { tree[now] = key; return; } int mid = (l+r)>>1;

	if (pos <= mid) modify(tree,now<<1,l,mid,pos,key);

	else modify(tree,now<<1|1,mid+1,r,pos,key);

	tree[now] = min(tree[now<<1],tree[now<<1|1]);

}



inline ll query(ll *tree,int now,int l,int r,int ql,int qr)

{

	if (ql == l&&qr == r) return tree[now]; int mid = (l+r)>>1;

	if (qr <= mid) return query(tree,now<<1,l,mid,ql,qr);

	else if (ql > mid) return query(tree,now<<1|1,mid+1,r,ql,qr);

	else return min(query(tree,now<<1,l,mid,ql,mid),query(tree,now<<1|1,mid+1,r,mid+1,qr));

}



int main()

{

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

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

	N = gi(); E = gi(); T = gi();

	for (int i = 1;i <= N;++i) X[i] = gi(),tree1[i] = tree2[i] = 1LL<<60;

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

	{

		modify(tree1,1,1,N,i,f[i-1]-2LL*(ll)X[i]-(ll)X[i-1]);

		modify(tree2,1,1,N,i,f[i-1]-(ll)X[i-1]);

		int l = 0,r = i-1,mid; f[i] = inf;

		while (l <= r)

		{

			mid = (l+r)>>1;

			if (T-2LL*(X[i]-X[mid+1]) > 0) r = mid-1;

			else l = mid+1;

		}

		if (r+1) f[i] = query(tree1,1,1,N,1,r+1)+3LL*X[i];

		if (r+2 <= i) f[i] = min(f[i],query(tree2,1,1,N,r+2,i)+(ll)X[i]+(ll)T);

	}

	cout << f[N]+(ll)E-(ll)X[N] << endl;

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.164189238699787x):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

    scanf("%d%d%d", &n, &E, &T);

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

        f[i] = min(f[pos] + T, f[i]);

    }

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

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;

typedef long long ll;



const int MAXN = 100005;



int n, e, T;

int x[MAXN];



void input()

{

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

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

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

}



ll f[MAXN];



void solve()

{

	f[0] = 0;

	ll minv = 1e18;

	int j = 0;

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

	{

		f[i] = f[i - 1] + T;

		while(2 * (x[i] - x[j + 1]) > T)

		{

			minv = min(minv, f[j] - 2 * x[j + 1]);

			j++;

		}

		f[i] = min(f[i], f[j] + T);

		f[i] = min(f[i], minv + 2 * x[i]);

	}

}



void output()

{

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

}



int main()

{

	input();

	solve();

	output();



	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.154640014933161x):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

    scanf("%d%d%d", &n, &E, &T);

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

        f[i] = min(f[pos] + T, f[i]);

    }

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

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define N 111111

#define M 444444

#define LL long long

using namespace std;

int n,i,k,j,a[N];LL f[N],V1[M],V2[M],E,T;

void ins(int k,int l,int r,int x,LL z1,LL z2){

	if(l==r){V1[k]=z1;V2[k]=z2;return;}

	int md=l+r>>1;

	if(x<=md)ins(k<<1,l,md,x,z1,z2);else ins(k<<1|1,md+1,r,x,z1,z2);

	V1[k]=min(V1[k<<1],V1[k<<1|1]);

	V2[k]=min(V2[k<<1],V2[k<<1|1]);

}

LL qu1(int k,int l,int r,int x,int y){

	if(x>y)return 1e18;

	if(x<=l&&r<=y)return V1[k];

	int md=l+r>>1;

	if(y<=md)return qu1(k<<1,l,md,x,y);

	if(x>md)return qu1(k<<1|1,md+1,r,x,y);

	return min(qu1(k<<1,l,md,x,y),qu1(k<<1|1,md+1,r,x,y));

}

LL qu2(int k,int l,int r,int x,int y){

	if(x>y)return 1e18;

	if(x<=l&&r<=y)return V2[k];

	int md=l+r>>1;

	if(y<=md)return qu2(k<<1,l,md,x,y);

	if(x>md)return qu2(k<<1|1,md+1,r,x,y);

	return min(qu2(k<<1,l,md,x,y),qu2(k<<1|1,md+1,r,x,y));

}

int main(){

	for(i=0;i<M;i++)V1[i]=V2[i]=1e18;

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

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

	for(i=0,k=0;i<=n;i++){

		f[i]=1e18;

		for(;(a[i]-a[k+1])*2>T&&k<i;k++);

		//f[i]=f[k]+max(a[i]-a[k+1]+a[i]-a[k+1],T)+a[i]-a[k];

		//j<=k a[i]-a[j+1*2>T

		//f[i]=qu2(1,0,0,k)

	//	printf("%d %d\n",(a[i]-a[k+1])*2,T);

		if(i==0)f[i]=0;else 

		f[i]=min(qu1(1,0,n,k,i-1)+T+a[i],qu2(1,0,n,0,k-1)+1ll*a[i]*3);

		//printf("%lld %lld\n",qu1(1,0,n,k,i-1)+T+a[i],qu2(1,0,n,0,k-1)+1ll*a[i]*3);

		//printf("%d %d %lld\n",i,k,f[i]);

	//	printf("%lld %lld %d\n",qu1(1,0,n,k,i-1),qu2(1,0,n,0,k-1),T+a[i]);

		//puts("-----------------------");

			//f[i]=min(f[i],f[j]+a[i]-a[j]+max((a[i]-a[j+1])*2,T));

		

		ins(1,0,n,i,f[i]-a[i],f[i]-a[i]-a[i+1]*2);

	}

	printf("%lld\n",f[n]+E-a[n]);

}

// Faster C++ solution for the same problem (measured speedup: 2.5077382395484493x):
#include <cstdio>

#include <algorithm>

#include <cstring>



typedef long long ll;



int n, e, t, x[100005];

ll dp[100005];



namespace SegTree {

	ll mn[100005 << 2];

	

	void init() { memset(mn, 0x3f, sizeof mn); }

	

	void modify(int k, int l, int r, int pos, ll val) {

		if (l == r) {

			mn[k] = val; return;

		}

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

		if (pos <= mid) modify(k << 1, l, mid, pos, val);

		else modify(k << 1 | 1, mid + 1, r, pos, val);

		mn[k] = std::min(mn[k << 1], mn[k << 1 | 1]);

	}

	

	ll query(int k, int l, int r, int L, int R) {

		if (L > R) return 0x3f3f3f3f3f3f3f3fll;

		if (L <= l && r <= R) return mn[k];

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

		ll res = 0x3f3f3f3f3f3f3f3fll;

		if (L <= mid) res = std::min(res, query(k << 1, l, mid, L, R));

		if (mid < R) res = std::min(res, query(k << 1 | 1, mid + 1, r, L, R));

		return res;

	}

}



int main() {

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

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

	

	SegTree::init();

	

	int l = 0;

	SegTree::modify(1, 0, n, 0, 0);

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

		while ((x[i] - x[l + 1]) * 2 >= t) {

			SegTree::modify(1, 0, n, l, dp[l] - x[l + 1] * 2);

			++l;

		}

		dp[i] = std::min(t + SegTree::query(1, 0, n, l, i - 1), 

						 x[i] * 2 + SegTree::query(1, 0, n, 0, l - 1));

		SegTree::modify(1, 0, n, i, dp[i]);

	}

	

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

	

	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

using namespace std;



const int MAXN=100005 ;

int n , E, T , dis[MAXN] ;

long long dp[MAXN] ;



multiset<long long> st;

multiset<long long>::iterator it ;



long long calc_1(int j){

	return dp[j]-2*dis[j+1]-dis[j] ;

}



long long calc_2(int j){

	return dp[j]-dis[j] ;

}



int main(){

	scanf("%d%d%d",&n,&E,&T) ;

	memset(dp,0x3f,sizeof(dp)) ;

	for(int i=1;i<=n;++i) scanf("%d",&dis[i]) ;

	dp[0]=0 ;

	int last=0 ; //第一个满足边界的

	st.insert(calc_2(0)) ;

	long long minn=(1ll<<60)-1 ;

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

		while(last<i && 2*(dis[i]-dis[last+1])>=T){

			long long tmp=calc_2(last) ;

			it=st.find(tmp) , st.erase(it) ;

			minn=min(minn,calc_1(last)) , ++last ;

		}

		dp[i]=minn+(long long)3*dis[i] ;

		if(!st.empty()) dp[i]=min(dp[i],(*st.begin())+T+dis[i]) ;

		st.insert(calc_2(i)) ;

	}

	cout << dp[n]+E-dis[n] << '\n' ;

	return 0 ;

}

// Faster C++ solution for the same problem (measured speedup: 1.8274200378547782x):
#include <bits/stdc++.h>

using namespace std;

long long f[112345];

int n,pp,s,t,d[112345];

int main(){

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

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

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

	pp = 1;

	long long mi = (1 << 31) - 1;

	f[0] = 0;

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

		while (pp <= n && 2 * (d[i] - d[pp]) > t){

			mi = min(mi,f[pp - 1] - d[pp] * 2);

			pp++;

		}

		f[i] = min(f[pp - 1] + t,mi + d[i] * 2);

	}

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

}
// Slower C++ solution:
#include<bits/stdc++.h>



using namespace std;



long long f[100010],c[100010],d[100010];

int x[100010];

int n,e,t,T;



inline void add1(int x,long long o)

{

	while(x<=n)

	{

		c[x]=min(c[x],o);

		x+=x&-x;

	}

}



inline long long ask1(int x)

{

	long long nowans=0x3f3f3f3f3f3f3f3fll;

	while(x)

	{

		nowans=min(nowans,c[x]);

		x-=x&-x;

	}

	return nowans;

}



inline void add2(int x,long long o)

{

	while(x)

	{

		d[x]=min(d[x],o);

		x-=x&-x;

	}

}



inline long long ask2(int x)

{

	long long nowans=0x3f3f3f3f3f3f3f3fll;

	while(x<=n)

	{

		nowans=min(nowans,d[x]);

		x+=x&-x;

	}

	return nowans;

}



int main()

{

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

	T=t;

	if(t%2)T++;

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

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

	memset(f,0x3f,sizeof(f));

	memset(c,0x3f,sizeof(c));

	memset(d,0x3f,sizeof(d));

	f[0]=0;

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

	{

		f[i]=min(f[i],f[i-1]+x[i]-x[i-1]+t);

		int now=upper_bound(x+1,x+1+i,x[i]-T/2)-x;

		if(x[i]-T/2>=x[1])

		{

			now--;

			long long nowans=ask1(now);

			f[i]=min(f[i],3ll*x[i]+nowans);

		}

		if(x[i]-T/2<x[1])now=0;

		now++;

		long long nowans=ask2(now);

		f[i]=min(f[i],x[i]+nowans);

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

		{

			if((x[j]-x[i])*2>=t)f[j]=min(f[j],f[i-1]+3ll*(x[j]-x[i])+x[i]-x[i-1]);

			else f[j]=min(f[j],f[i-1]+t-2*(x[j]-x[i])+3ll*(x[j]-x[i])+x[i]-x[i-1]);

		}*/

		add1(i,-3ll*x[i]+f[i-1]+x[i]-x[i-1]);

		add2(i,0ll+t-x[i]+x[i]+f[i-1]-x[i-1]);

	}

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

}

// Faster C++ solution for the same problem (measured speedup: 3.4440943250954437x):
#include <bits/stdc++.h>

using namespace std;

long long f[112345];

int n,pp,s,t,d[112345];

int main(){

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

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

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

	pp = 1;

	long long mi = (1 << 31) - 1;

	f[0] = 0;

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

		while (pp <= n && 2 * (d[i] - d[pp]) > t){

			mi = min(mi,f[pp - 1] - d[pp] * 2);

			pp++;

		}

		f[i] = min(f[pp - 1] + t,mi + d[i] * 2);

	}

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

}