stablegradients/pie-gem5-pairs huggingface dataset:
// 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: 4.756930452685206x):
#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

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

long long f[maxn];

struct Seg {

	long long tr[maxn << 2];

	inline void Upd(int o, int l, int r, int p, long long d) {

		if(l == r)

			return tr[o] = d, void();

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

		if(p <= mid)

			Upd(o << 1, l, mid, p, d);

		else

			Upd(o << 1 | 1, mid + 1, r, p, d);

		tr[o] = min(tr[o << 1], tr[o << 1 | 1]);

	}

	inline long long Ask(int o, int l, int r, int ql, int qr) {

		if(ql > qr)

			return 1e18;

		if(ql <= l && r <= qr)

			return tr[o];

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

		long long ans = 1e18;

		if(ql <= mid)

			ans = min(ans, Ask(o << 1, l, mid, ql, qr));

		if(qr > mid)

			ans = min(ans, Ask(o << 1 | 1, mid + 1, r, ql, qr));

		return ans;

	}

}g, h;

int main() {

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

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

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

	memset(f, 0x3f, sizeof f);

	f[0] = 0, g.Upd(1, 0, n, 0, 0), h.Upd(1, 0, n, 0, - 1ll * 2 * x[1]);

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

		int p = lower_bound(x, x + i, x[i] - t / 2) - x;

		f[i] = min(g.Ask(1, 0, n, p - 1, i - 1) + t + x[i], h.Ask(1, 0, n, 0, p - 2) + 1ll * 3 * x[i]);

		if(i < n)

			g.Upd(1, 0, n, i, f[i] - x[i]), h.Upd(1, 0, n, i, f[i] - x[i] - 1ll * 2 * x[i + 1]);

		

	}

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



}
// Slower C++ solution:
#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;

}


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

using namespace std;

const int maxn = 1e5 + 5;

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

long long f[maxn];

struct Seg {

	long long tr[maxn << 2];

	inline void Upd(int o, int l, int r, int p, long long d) {

		if(l == r)

			return tr[o] = d, void();

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

		if(p <= mid)

			Upd(o << 1, l, mid, p, d);

		else

			Upd(o << 1 | 1, mid + 1, r, p, d);

		tr[o] = min(tr[o << 1], tr[o << 1 | 1]);

	}

	inline long long Ask(int o, int l, int r, int ql, int qr) {

		if(ql > qr)

			return 1e18;

		if(ql <= l && r <= qr)

			return tr[o];

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

		long long ans = 1e18;

		if(ql <= mid)

			ans = min(ans, Ask(o << 1, l, mid, ql, qr));

		if(qr > mid)

			ans = min(ans, Ask(o << 1 | 1, mid + 1, r, ql, qr));

		return ans;

	}

}g, h;

int main() {

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

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

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

	memset(f, 0x3f, sizeof f);

	f[0] = 0, g.Upd(1, 0, n, 0, 0), h.Upd(1, 0, n, 0, - 1ll * 2 * x[1]);

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

		int p = lower_bound(x, x + i, x[i] - t / 2) - x;

		f[i] = min(g.Ask(1, 0, n, p - 1, i - 1) + t + x[i], h.Ask(1, 0, n, 0, p - 2) + 1ll * 3 * x[i]);

		if(i < n)

			g.Upd(1, 0, n, i, f[i] - x[i]), h.Upd(1, 0, n, i, f[i] - x[i] - 1ll * 2 * x[i + 1]);

		

	}

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



}
// Slower C++ solution:
/* --- author: dxm --- */

#include<bits/stdc++.h>

using namespace std;



#define ll long long

#define INF 2147483647

#define Inf 1e18

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

#define REP(i,n) for(int (i)=1;(i)<=n;i++)

#define mp make_pair

#define pb push_back

#define pii pair<int,int>

inline void Fail(){

	printf("0");

	exit(0);

}



const int maxn=100005;

int n,e,t;

ll dp[maxn];

int x[maxn],y[maxn];

class segtree{

public:

	ll tree[maxn*4];

	int leaf[maxn];

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

		if(l==r){

			leaf[l]=node;

			tree[node]=Inf;

			return;

		}

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

		build(l,mid,node*2);

		build(mid+1,r,node*2+1); 

		tree[node]=min(tree[node*2],tree[node*2+1]);

	}

	void upd(int node,ll val){

		node=leaf[node];

		tree[node]=val;

		node>>=1;

		while(node){

			tree[node]=min(tree[node*2],tree[node*2+1]);

			node>>=1;

		}

	}

	ll query(int l,int r,int vl,int vr,int node){

		if(r<l||vr<vl)return Inf;

		if(l>vr||r<vl)return Inf;

		if(l>=vl&&r<=vr)return tree[node];

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

		return min(query(l,mid,vl,vr,node*2),query(mid+1,r,vl,vr,node*2+1));

	}

}t1,t2;



int main(){

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

	rep(i,n)scanf("%d",&x[i]),y[i]=2*x[i];

	t1.build(0,n-1,1);

	t2.build(0,n-1,1);

	rep(i,n){

		dp[i]=max((x[i]-x[0])*2LL,1LL*t);

		int pos=lower_bound(y,y+n,2*x[i]-t)-y;

		dp[i]=min(dp[i],min(t1.query(0,n-1,0,pos-2,1)+2LL*x[i],t2.query(0,n-1,max(pos-1,0),n-1,1)+t));

		t1.upd(i,dp[i]-2LL*x[i+1]);

		t2.upd(i,dp[i]);

	}

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

	return 0;

}



/*

Input:

-----------------

Output:

*/

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

#include<algorithm>

#define INF 2100000006

#define MAXN 100006

using namespace std;

long long m,T,minone,a[MAXN],d[MAXN];

int n,l[MAXN],last;

int find(int x)

{

	int l=1,r=x;

	while(l<r)

	{

		int mid=(l+r)/2;

		if(T-2*(a[x]-a[mid])>0) r=mid;

		else l=mid+1;

	}

	return l;

}

int main()

{

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

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

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

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

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

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

		l[i]=find(i);

	minone=INF;

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

	{

		while(last<l[i]-1)

		{

			last++;

			minone=min(minone,d[last-1]-a[last-1]-2*a[last]);

		}

		long long len=a[i]-a[l[i]];

		d[i]=d[l[i]-1]+a[l[i]]-a[l[i]-1]+len+T;

		d[i]=min(d[i],minone+3*a[i]);

	}

	printf("%lld",d[n]+m-a[n]);

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

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<LL> 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 = 100100;



int A[MAX];

LL A2[MAX];



LL D[MAX];



VI ADD[MAX];

VI REM[MAX];



LL ST[MAX];



multiset<LL> S;



int main()

{

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

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



	int n, e, t;

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

	FOR (i, 0, n)

	{

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

		A2[i] = A[i] * 2;

	}



	FOR (i, 0, n + 7)

	{

		ST[i] = LINF;

	}





	LL res = e;



	D[0] = 0;

	LL mn = LINF;



	FOR (i, 0, n + 1)

	{

		FOR (j, 0, SZ(ADD[i]))

		{

			S.insert(ADD[i][j]);

		}



		FOR (j, 0, SZ(REM[i]))

		{

			S.erase(S.find(REM[i][j]));

		}



		mn = min(mn, ST[i]);



		if (i == 0) D[i] = 0;

		else

		{

			D[i] = LINF;

			if (SZ(S))D[i] = *S.begin();



			D[i] = min(D[i], 2 * A[i - 1] + mn);



	//		cout<<i<<' '<<mn<<endl;

	//		if (SZ(S)) cout<<"** "<<*S.begin()<<endl;



			if (i == n) break;

		}



		int pos = upper_bound(A2, A2 + n, A2[i] + t) - A2;



	//	cout<<i<<": "<<pos<<endl;



		ADD[i+1].PB(D[i] + t);

		REM[pos + 1].PB(D[i] + t);



		ST[pos + 1] = min(ST[pos + 1], D[i] - 2 * A[i]);

		//mn = min(mn, D[i] - 2 * A[i]);

	}





/*	FOR (i, 0, n + 1)

	{

		cout<<D[i]<<' ';

	}

	cout<<endl;*/



	res += D[n];



	cout<<res<<endl;





}






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

#include<algorithm>

#define INF 2100000006

#define MAXN 100006

using namespace std;

long long m,T,minone,a[MAXN],d[MAXN];

int n,l[MAXN],last;

int find(int x)

{

	int l=1,r=x;

	while(l<r)

	{

		int mid=(l+r)/2;

		if(T-2*(a[x]-a[mid])>0) r=mid;

		else l=mid+1;

	}

	return l;

}

int main()

{

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

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

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

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

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

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

		l[i]=find(i);

	minone=INF;

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

	{

		while(last<l[i]-1)

		{

			last++;

			minone=min(minone,d[last-1]-a[last-1]-2*a[last]);

		}

		long long len=a[i]-a[l[i]];

		d[i]=d[l[i]-1]+a[l[i]]-a[l[i]-1]+len+T;

		d[i]=min(d[i],minone+3*a[i]);

	}

	printf("%lld",d[n]+m-a[n]);

}
// Slower C++ solution:
/* --- author: dxm --- */

#include<bits/stdc++.h>

using namespace std;



#define ll long long

#define INF 2147483647

#define Inf 1e18

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

#define REP(i,n) for(int (i)=1;(i)<=n;i++)

#define mp make_pair

#define pb push_back

#define pii pair<int,int>

inline void Fail(){

	printf("0");

	exit(0);

}



const int maxn=100005;

int n,e,t;

ll dp[maxn];

int x[maxn],y[maxn];

class segtree{

public:

	ll tree[maxn*4];

	int leaf[maxn];

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

		if(l==r){

			leaf[l]=node;

			tree[node]=Inf;

			return;

		}

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

		build(l,mid,node*2);

		build(mid+1,r,node*2+1); 

		tree[node]=min(tree[node*2],tree[node*2+1]);

	}

	void upd(int node,ll val){

		node=leaf[node];

		tree[node]=val;

		node>>=1;

		while(node){

			tree[node]=min(tree[node*2],tree[node*2+1]);

			node>>=1;

		}

	}

	ll query(int l,int r,int vl,int vr,int node){

		if(r<l||vr<vl)return Inf;

		if(l>vr||r<vl)return Inf;

		if(l>=vl&&r<=vr)return tree[node];

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

		return min(query(l,mid,vl,vr,node*2),query(mid+1,r,vl,vr,node*2+1));

	}

}t1,t2;



int main(){

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

	rep(i,n)scanf("%d",&x[i]),y[i]=2*x[i];

	t1.build(0,n-1,1);

	t2.build(0,n-1,1);

	rep(i,n){

		dp[i]=max((x[i]-x[0])*2LL,1LL*t);

		int pos=lower_bound(y,y+n,2*x[i]-t)-y;

		dp[i]=min(dp[i],min(t1.query(0,n-1,0,pos-2,1)+2LL*x[i],t2.query(0,n-1,max(pos-1,0),n-1,1)+t));

		t1.upd(i,dp[i]-2LL*x[i+1]);

		t2.upd(i,dp[i]);

	}

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

	return 0;

}



/*

Input:

-----------------

Output:

*/

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

#include <cstdio>



#define REDIRECT(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

#define CLOSEALL() fclose(stdin), fclose(stdout)



const int MAXN = 1e5 + 10;



typedef long long i64;



i64 tmp = 0x7F7F7F7F7F7F7F7F;

i64 N, M, T;

i64 a[MAXN];

i64 dp[MAXN];



int main()

{

	//REDIRECT("computer");



	i64 t = 0;

	scanf("%lld%lld%lld", &N, &M, &T);

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

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



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

	{

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

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

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

	}



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



	CLOSEALL();

	return 0;

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

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<LL> 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 = 100100;



int A[MAX];

LL A2[MAX];



LL D[MAX];



VI ADD[MAX];

VI REM[MAX];



LL ST[MAX];



multiset<LL> S;



int main()

{

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

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



	int n, e, t;

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

	FOR (i, 0, n)

	{

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

		A2[i] = A[i] * 2;

	}



	FOR (i, 0, n + 7)

	{

		ST[i] = LINF;

	}





	LL res = e;



	D[0] = 0;

	LL mn = LINF;



	FOR (i, 0, n + 1)

	{

		FOR (j, 0, SZ(ADD[i]))

		{

			S.insert(ADD[i][j]);

		}



		FOR (j, 0, SZ(REM[i]))

		{

			S.erase(S.find(REM[i][j]));

		}



		mn = min(mn, ST[i]);



		if (i == 0) D[i] = 0;

		else

		{

			D[i] = LINF;

			if (SZ(S))D[i] = *S.begin();



			D[i] = min(D[i], 2 * A[i - 1] + mn);



	//		cout<<i<<' '<<mn<<endl;

	//		if (SZ(S)) cout<<"** "<<*S.begin()<<endl;



			if (i == n) break;

		}



		int pos = upper_bound(A2, A2 + n, A2[i] + t) - A2;



	//	cout<<i<<": "<<pos<<endl;



		ADD[i+1].PB(D[i] + t);

		REM[pos + 1].PB(D[i] + t);



		ST[pos + 1] = min(ST[pos + 1], D[i] - 2 * A[i]);

		//mn = min(mn, D[i] - 2 * A[i]);

	}





/*	FOR (i, 0, n + 1)

	{

		cout<<D[i]<<' ';

	}

	cout<<endl;*/



	res += D[n];



	cout<<res<<endl;





}






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

#include <cstdio>



#define REDIRECT(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

#define CLOSEALL() fclose(stdin), fclose(stdout)



const int MAXN = 1e5 + 10;



typedef long long i64;



i64 tmp = 0x7F7F7F7F7F7F7F7F;

i64 N, M, T;

i64 a[MAXN];

i64 dp[MAXN];



int main()

{

	//REDIRECT("computer");



	i64 t = 0;

	scanf("%lld%lld%lld", &N, &M, &T);

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

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



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

	{

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

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

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

	}



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



	CLOSEALL();

	return 0;

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

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<LL> 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 = 100100;



int A[MAX];

LL A2[MAX];



LL D[MAX];



VI ADD[MAX];

VI REM[MAX];



LL ST[MAX];



multiset<LL> S;



int main()

{

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

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



	int n, e, t;

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

	FOR (i, 0, n)

	{

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

		A2[i] = A[i] * 2;

	}



	FOR (i, 0, n + 7)

	{

		ST[i] = LINF;

	}





	LL res = e;



	D[0] = 0;

	LL mn = LINF;



	FOR (i, 0, n + 1)

	{

		FOR (j, 0, SZ(ADD[i]))

		{

			S.insert(ADD[i][j]);

		}



		FOR (j, 0, SZ(REM[i]))

		{

			S.erase(S.find(REM[i][j]));

		}



		mn = min(mn, ST[i]);



		if (i == 0) D[i] = 0;

		else

		{

			D[i] = LINF;

			if (SZ(S))D[i] = *S.begin();



			D[i] = min(D[i], 2 * A[i - 1] + mn);



	//		cout<<i<<' '<<mn<<endl;

	//		if (SZ(S)) cout<<"** "<<*S.begin()<<endl;



			if (i == n) break;

		}



		int pos = upper_bound(A2, A2 + n, A2[i] + t) - A2;



	//	cout<<i<<": "<<pos<<endl;



		ADD[i+1].PB(D[i] + t);

		REM[pos + 1].PB(D[i] + t);



		ST[pos + 1] = min(ST[pos + 1], D[i] - 2 * A[i]);

		//mn = min(mn, D[i] - 2 * A[i]);

	}





/*	FOR (i, 0, n + 1)

	{

		cout<<D[i]<<' ';

	}

	cout<<endl;*/



	res += D[n];



	cout<<res<<endl;





}






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

using namespace std;



#define int long long



const int N = 1e5 + 5;



int A[N], n, T, E, dp[N];



int calc(int x, int y) {

	if(y == x + 1) return dp[x] + A[y] - A[x] + T;

	else return dp[x] + A[x + 1] - A[x] + (A[y] - A[x + 1]) * 3 + max(0LL, T - (A[y] - A[x + 1]) * 2);

}



multiset <int> C, D;



main() {

	cin >> n >> E >> T;

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

	int ans = 1e18, res = 0;

	dp[0] = 0;

	int cur = 0, cnt = 1000;

	int now = 0;

	C.insert(dp[0] - A[0] + T);

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

		dp[i] = 1e18;

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

			C.erase(C.find(dp[now] - A[now] + T));

			D.insert((dp[now] - A[now + 1] * 2 - A[now])); 

			++ now;

		}



		if(C.size()) dp[i] = min(dp[i], *C.begin() + A[i]);

		if(D.size()) dp[i] = min(dp[i], *D.begin() + A[i] * 3);



		C.insert(dp[i] - A[i] + T);

		dp[i] = min(dp[i], calc(i - 1, i));

	}

	cout << dp[n] + E - A[n] << endl;

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

using namespace std;



#define int long long

typedef vector<int>vint;

typedef pair<int,int>pint;

typedef vector<pint>vpint;

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

#define reps(i,f,n) for(int i=(f);i<(n);i++)

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

#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)

#define pb push_back

#define fi first

#define se second

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}

template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}



const int INF=1001001001001001001ll;

struct segtree{

    static const int SEG=1<<17;

    vint dat;

    segtree():dat(SEG*2){}

    void update(int k,int x){

        k+=SEG-1;

        dat[k]=x;

        while(k){

            k=(k-1)/2;

            dat[k]=min(dat[k*2+1],dat[k*2+2]);

        }

    }

    int query(int a,int b,int k=0,int l=0,int r=SEG){

        if(r<=a||b<=l)return INF;

        if(a<=l&&r<=b)return dat[k];

        return min(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));

    }

};



int N,E,T;

int X[111111];

int dp[111111];

signed main(){

    cin>>N>>E>>T;

    X[0]=0;

    for(int i=1;i<=N;i++)cin>>X[i];



    segtree segA;

    segtree segB;

    segA.update(0,-2*X[1]);

    segB.update(0,0);

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

        int lb=-1,ub=i;

        while(ub-lb>1){

            int mid=(ub+lb)/2;

            if(2*(X[i]-X[mid+1])<T)ub=mid;

            else lb=mid;

        }

        int val=INF;

        if(ub)val=segA.query(0,ub)+3*X[i];

        if(ub!=i)chmin(val,segB.query(ub,i)+T+X[i]);

        dp[i]=val;

        segA.update(i,val-X[i]-2*X[i+1]);

        segB.update(i,val-X[i]);

    }

    cout<<dp[N]+E-X[N]<<endl;

    return 0;

}


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

using namespace std;



#define int long long



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

#define pb push_back

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

#define fi first

#define se second

typedef vector<int>vint;

typedef pair<int,int>pint;

typedef vector<pint>vpint;



template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}

template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}



const int INF=1001001001001001001ll;



int N,E,T;

int X[111111];

int dp[111111];



signed main(){

    cin>>N>>E>>T;

    rep(i,N)cin>>X[i+1];



    int ei=INF;

    int L=1;

    deque<pint>deq;

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

        int tmp=dp[i-1]+X[i]-X[i-1];

        while(deq.size()&&deq.back().fi>T+tmp-X[i])deq.pop_back();

        deq.push_back({T+tmp-X[i],i});

        while((X[i]-X[L])*2>T){

            chmin(ei,dp[L-1]+X[L]-X[L-1]-3*X[L]);

            if(deq.front().se==L)deq.pop_front();

            L++;

        }



        dp[i]=min(deq.front().fi+X[i],ei+3*X[i]);

    }



    cout<<dp[N]+E-X[N]<<endl;

    return 0;

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

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

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

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

using namespace std;

typedef long long ll;

const int N=1e5+10,inf=(1<<30);

ll f[N],p[N];int n,e,t;

int main()

{

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

	fo(i,1,n) scanf("%lld",&p[i]);

	memset(f,63,sizeof(f));f[0]=0;

	ll mn=inf;

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

		for(;t<=(p[i]-p[j+1])<<1;j++)

			mn=min(mn,f[j]-2*p[j+1]);

			if(j<i) f[i]=min(f[i],f[j]+t);

			f[i]=min(f[i],mn+2*p[i]);

	}

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

	return 0;

}

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

#include<algorithm>

typedef long long LL;

const int MAXN = 100000+10;

const int INF = 0x3f3f3f3f;

int n, t, e;

LL x[MAXN], f[MAXN];

int main(){

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

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

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

    int j=0;

    LL mn = 1e14;

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

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

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

            j++;

        }

        f[i] = std::min(f[j]+t, mn + 2*x[i]);

    }

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

    return 0;

}