stablegradients/pie-gem5-pairs huggingface dataset:
// 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.4352345982604793x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 100000

#define INF 1000000000000000000LL

using namespace std;

typedef long long LL;

LL p[MAXN+5];

LL dp[MAXN+5];

int N;

LL M;

LL T;

void Init()

{

	memset(dp,-1,sizeof(dp));

}

LL GetVal(int i,int j)

{

	return dp[j-1]+T-2LL*(p[i]-p[j])+3LL*(p[i]-p[j])+p[j]-p[j-1];

}

int main()

{

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

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

	Init();

	dp[0]=0;

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

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

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

	LL minval=INF;

	int pn=-1;

	dp[0]=0;

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

	{

		int pos=lower_bound(p+1,p+1+N,p[i]-T/2)-p;

		if(2*(p[i]-p[pos])==T)

			pos++;

		if(2*(p[i]-p[pos-1])>=T)

			while(pn<pos-1)

			{

				pn++;

				if(pn!=0)	minval=min(dp[pn-1]-2LL*p[pn]-p[pn-1],minval);

				else		minval=min(-3LL*p[pn],minval);

			}

		dp[i]=GetVal(i,pos);

		dp[i]=min(dp[i],minval+3LL*p[i]);

	}

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

	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: 8.603145104526089x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 100000

#define INF 1000000000000000000LL

using namespace std;

typedef long long LL;

LL p[MAXN+5];

LL dp[MAXN+5];

int N;

LL M;

LL T;

void Init()

{

	memset(dp,-1,sizeof(dp));

}

LL GetVal(int i,int j)

{

	return dp[j-1]+T-2LL*(p[i]-p[j])+3LL*(p[i]-p[j])+p[j]-p[j-1];

}

int main()

{

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

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

	Init();

	dp[0]=0;

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

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

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

	LL minval=INF;

	int pn=-1;

	dp[0]=0;

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

	{

		int pos=lower_bound(p+1,p+1+N,p[i]-T/2)-p;

		if(2*(p[i]-p[pos])==T)

			pos++;

		if(2*(p[i]-p[pos-1])>=T)

			while(pn<pos-1)

			{

				pn++;

				if(pn!=0)	minval=min(dp[pn-1]-2LL*p[pn]-p[pn-1],minval);

				else		minval=min(-3LL*p[pn],minval);

			}

		dp[i]=GetVal(i,pos);

		dp[i]=min(dp[i],minval+3LL*p[i]);

	}

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

	return 0;

}
// 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: 3.430639198641081x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 100000

#define INF 1000000000000000000LL

using namespace std;

typedef long long LL;

LL p[MAXN+5];

LL dp[MAXN+5];

int N;

LL M;

LL T;

void Init()

{

	memset(dp,-1,sizeof(dp));

}

LL GetVal(int i,int j)

{

	return dp[j-1]+T-2LL*(p[i]-p[j])+3LL*(p[i]-p[j])+p[j]-p[j-1];

}

int main()

{

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

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

	Init();

	dp[0]=0;

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

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

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

	LL minval=INF;

	int pn=-1;

	dp[0]=0;

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

	{

		int pos=lower_bound(p+1,p+1+N,p[i]-T/2)-p;

		if(2*(p[i]-p[pos])==T)

			pos++;

		if(2*(p[i]-p[pos-1])>=T)

			while(pn<pos-1)

			{

				pn++;

				if(pn!=0)	minval=min(dp[pn-1]-2LL*p[pn]-p[pn-1],minval);

				else		minval=min(-3LL*p[pn],minval);

			}

		dp[i]=GetVal(i,pos);

		dp[i]=min(dp[i],minval+3LL*p[i]);

	}

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

	return 0;

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

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cstdlib>



#define cmax(_a, _b) (_a < (_b) ? _a = (_b), 1 : 0)

#define cmin(_a, _b) (_a > (_b) ? _a = (_b), 1 : 0)

#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))

#define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))



#define maxn 100010

#define lowbit(_x) ((_x) & (-(_x)))

typedef long long ll;

typedef double db;



const ll inf = 0x7ffffffffff;

ll f[maxn];

int x[maxn], hash[maxn], hcnt;

ll tr1[maxn], tr2[maxn];

void modify1(int pos, ll val)

{

	for (; pos <= hcnt; pos += lowbit(pos)) cmin(tr1[pos], val);

}

void modify2(int pos, ll val)

{

	for (; pos; pos -= lowbit(pos)) cmin(tr2[pos], val);

}

ll query1(int pos)

{

	ll ret = inf;

	for (; pos; pos -= lowbit(pos)) cmin(ret, tr1[pos]);

	return ret;

}

ll query2(int pos)

{

	ll ret = inf;

	for (; pos <= hcnt; pos += lowbit(pos)) cmin(ret, tr2[pos]);

	return ret;

}

int main()

{

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

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

	for (int i = 0; i <= n; ++i) hash[++hcnt] = 2 * x[i];



	memset(tr1, 63, sizeof (tr1));

	memset(tr2, 63, sizeof (tr2));

	f[0] = 0;

	modify1(2, -2 * x[1]);

	modify2(2, 0);

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

	{

		f[i] = inf;



		int pos = std::upper_bound(hash + 1, hash + hcnt + 1, 2 * x[i] - T) - hash - 1;

//		printf("pos %d\n", pos);

		ll tmp = query1(pos) + 3ll * x[i];

		cmin(f[i], tmp);

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



		pos = std::lower_bound(hash + 1, hash + hcnt + 1, 2 * x[i] - T) - hash;

//		printf("pos %d\n", pos);

		tmp = query2(pos) + T + x[i];

		cmin(f[i], tmp);

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

		

		modify1(i + 2, f[i] - 2ll * x[i + 1] - x[i]);

		modify2(i + 2, f[i] - x[i]);

		

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

	}

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

	return 0;

}

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

#include<cstring>

#include<algorithm>

#define MAXN 100000

#define INF 1000000000000000000LL

using namespace std;

typedef long long LL;

LL p[MAXN+5];

LL dp[MAXN+5];

int N;

LL M;

LL T;

void Init()

{

	memset(dp,-1,sizeof(dp));

}

LL GetVal(int i,int j)

{

	return dp[j-1]+T-2LL*(p[i]-p[j])+3LL*(p[i]-p[j])+p[j]-p[j-1];

}

int main()

{

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

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

	Init();

	dp[0]=0;

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

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

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

	LL minval=INF;

	int pn=-1;

	dp[0]=0;

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

	{

		int pos=lower_bound(p+1,p+1+N,p[i]-T/2)-p;

		if(2*(p[i]-p[pos])==T)

			pos++;

		if(2*(p[i]-p[pos-1])>=T)

			while(pn<pos-1)

			{

				pn++;

				if(pn!=0)	minval=min(dp[pn-1]-2LL*p[pn]-p[pn-1],minval);

				else		minval=min(-3LL*p[pn],minval);

			}

		dp[i]=GetVal(i,pos);

		dp[i]=min(dp[i],minval+3LL*p[i]);

	}

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

	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.821891630788303x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

#define maxn 100005

#define INF (LL)1e16

using namespace std;

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

LL dp[maxn];

int main()

{

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

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

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

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

	dp[0]=0;

	LL mn=INF; int now=0;

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

	{

		dp[i]=dp[i-1]+t+x[i]-x[i-1];

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

		{

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

			now++;

		}

		dp[i]=min(2*x[i]+mn,dp[now]+t);

	}

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

}
// 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.4336750700746785x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

#define maxn 100005

#define INF (LL)1e16

using namespace std;

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

LL dp[maxn];

int main()

{

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

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

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

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

	dp[0]=0;

	LL mn=INF; int now=0;

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

	{

		dp[i]=dp[i-1]+t+x[i]-x[i-1];

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

		{

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

			now++;

		}

		dp[i]=min(2*x[i]+mn,dp[now]+t);

	}

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

}
// 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: 8.599239447752652x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

#define maxn 100005

#define INF (LL)1e16

using namespace std;

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

LL dp[maxn];

int main()

{

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

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

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

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

	dp[0]=0;

	LL mn=INF; int now=0;

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

	{

		dp[i]=dp[i-1]+t+x[i]-x[i-1];

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

		{

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

			now++;

		}

		dp[i]=min(2*x[i]+mn,dp[now]+t);

	}

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

}
// 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: 3.4290817566753122x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

#define maxn 100005

#define INF (LL)1e16

using namespace std;

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

LL dp[maxn];

int main()

{

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

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

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

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

	dp[0]=0;

	LL mn=INF; int now=0;

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

	{

		dp[i]=dp[i-1]+t+x[i]-x[i-1];

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

		{

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

			now++;

		}

		dp[i]=min(2*x[i]+mn,dp[now]+t);

	}

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

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

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cstdlib>



#define cmax(_a, _b) (_a < (_b) ? _a = (_b), 1 : 0)

#define cmin(_a, _b) (_a > (_b) ? _a = (_b), 1 : 0)

#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))

#define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))



#define maxn 100010

#define lowbit(_x) ((_x) & (-(_x)))

typedef long long ll;

typedef double db;



const ll inf = 0x7ffffffffff;

ll f[maxn];

int x[maxn], hash[maxn], hcnt;

ll tr1[maxn], tr2[maxn];

void modify1(int pos, ll val)

{

	for (; pos <= hcnt; pos += lowbit(pos)) cmin(tr1[pos], val);

}

void modify2(int pos, ll val)

{

	for (; pos; pos -= lowbit(pos)) cmin(tr2[pos], val);

}

ll query1(int pos)

{

	ll ret = inf;

	for (; pos; pos -= lowbit(pos)) cmin(ret, tr1[pos]);

	return ret;

}

ll query2(int pos)

{

	ll ret = inf;

	for (; pos <= hcnt; pos += lowbit(pos)) cmin(ret, tr2[pos]);

	return ret;

}

int main()

{

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

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

	for (int i = 0; i <= n; ++i) hash[++hcnt] = 2 * x[i];



	memset(tr1, 63, sizeof (tr1));

	memset(tr2, 63, sizeof (tr2));

	f[0] = 0;

	modify1(2, -2 * x[1]);

	modify2(2, 0);

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

	{

		f[i] = inf;



		int pos = std::upper_bound(hash + 1, hash + hcnt + 1, 2 * x[i] - T) - hash - 1;

//		printf("pos %d\n", pos);

		ll tmp = query1(pos) + 3ll * x[i];

		cmin(f[i], tmp);

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



		pos = std::lower_bound(hash + 1, hash + hcnt + 1, 2 * x[i] - T) - hash;

//		printf("pos %d\n", pos);

		tmp = query2(pos) + T + x[i];

		cmin(f[i], tmp);

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

		

		modify1(i + 2, f[i] - 2ll * x[i + 1] - x[i]);

		modify2(i + 2, f[i] - x[i]);

		

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

	}

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

	return 0;

}

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

#include<cstring>

#include<algorithm>

#define LL long long

#define maxn 100005

#define INF (LL)1e16

using namespace std;

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

LL dp[maxn];

int main()

{

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

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

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

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

	dp[0]=0;

	LL mn=INF; int now=0;

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

	{

		dp[i]=dp[i-1]+t+x[i]-x[i-1];

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

		{

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

			now++;

		}

		dp[i]=min(2*x[i]+mn,dp[now]+t);

	}

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

}
// 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: 1.8994416430319263x):
#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]);



}