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.3916740514627692x):
#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;

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

using namespace std;

const int N = 1e5 + 5;

int d[N], T;

long long dp[N];

long long calc_big(int j) {

	return T - d[j] + dp[j];

}

long long calc_small(int j) {

	return 2LL * (-d[j + 1]) - d[j] + dp[j];

}

struct cmp_big {

	bool operator () (const int &i, const int &j) {

		return calc_big(i) > calc_big(j);

	}

};

struct cmp_small {

	bool operator () (const int &i, const int &j) {

		return calc_small(i) > calc_small(j);

	}

};

int main() {

	int n, E;

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

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

	priority_queue<int, vector<int>, cmp_big> q1;

	priority_queue<int, vector<int>, cmp_small> q2;

	q1.push(0);

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

		while (!q1.empty() && 2LL * (d[i] - d[q1.top() + 1]) >= T) {

			q2.push(q1.top());

			q1.pop();

		}

		dp[i] = 1e18;

		if (!q1.empty()) {

			int j = q1.top();

			dp[i] = min(dp[i], d[i] + calc_big(j));

		}

		if (!q2.empty()) {

			int j = q2.top();

			dp[i] = min(dp[i], 3LL * d[i] + calc_small(j));

		}

		q1.push(i);

	}

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

}




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

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=100000+10;

ll f[maxn],xx[maxn];

ll n,e,t;

ll store;//fj-2xj+1

int main(){

	ll b1,b2,b3,b4;

	ll p;//定位

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

	

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

		scanf("%lld",&xx[b1]);

	}

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

		f[maxn]=b1*t;

	}

	p=0;store=((ll)1<<60);

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

		while (2*xx[p+1]<=2*xx[b1]-t){

			store=min(store,f[p]-2*xx[p+1]);

			p++;

		}

		f[b1]=min(2*xx[b1]+store,f[p]+t);

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

	}

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

	

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

using namespace std;



typedef long long ll;

const int maxn=100010;

int n,e;

ll T;

int x[maxn];

ll f[maxn];



int main()

{

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

	cin>>T;

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

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

	f[0]=0;

	f[1]=T;

	int la=0;

	ll minx=1LL<<60;

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

	{

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

		{

			ll tmp=f[la]-2LL*x[la+1];

			if (minx>tmp)	minx=tmp;

			la++;

		}

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

		if (la>0)

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

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

	}

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

	return 0;

}

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

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=100000+10;

ll f[maxn],xx[maxn];

ll n,e,t;

ll store;//fj-2xj+1

int main(){

	ll b1,b2,b3,b4;

	ll p;//定位

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

	

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

		scanf("%lld",&xx[b1]);

	}

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

		f[maxn]=b1*t;

	}

	p=0;store=((ll)1<<60);

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

		while (2*xx[p+1]<=2*xx[b1]-t){

			store=min(store,f[p]-2*xx[p+1]);

			p++;

		}

		f[b1]=min(2*xx[b1]+store,f[p]+t);

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

	}

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

	

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

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<set>

#define LL long long

using namespace std;

multiset<LL> s1, s2;

LL dp[110000], dp2[110000];

int x[110000], n, E, T;

int main(){

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

	dp2[0] = T;s1.insert(T);

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

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

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

			s1.erase(s1.find(dp2[j]));

			dp2[j] = dp2[j] - T - 2 * (x[j + 1]);

			s2.insert(dp2[j]);

			j++;

		}

		dp2[i] = (((LL)1)<<50);

		if(!s1.empty()) dp[i] = max(dp[i], *s1.begin() + x[i]);

		if(!s2.empty()) dp[i] = min(dp[i], *s2.begin() + (LL)3 * x[i]);

		dp2[i] = dp[i] - x[i] + T; 

		s1.insert(dp2[i]);

	}

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

	return 0;

}

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

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=100000+10;

ll f[maxn],xx[maxn];

ll n,e,t;

ll store;//fj-2xj+1

int main(){

	ll b1,b2,b3,b4;

	ll p;//定位

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

	

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

		scanf("%lld",&xx[b1]);

	}

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

		f[maxn]=b1*t;

	}

	p=0;store=((ll)1<<60);

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

		while (2*xx[p+1]<=2*xx[b1]-t){

			store=min(store,f[p]-2*xx[p+1]);

			p++;

		}

		f[b1]=min(2*xx[b1]+store,f[p]+t);

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

	}

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

	

}
// 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: 9.442486236093844x):
#include<cmath>

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=100000+10;

ll f[maxn],xx[maxn];

ll n,e,t;

ll store;//fj-2xj+1

int main(){

	ll b1,b2,b3,b4;

	ll p;//定位

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

	

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

		scanf("%lld",&xx[b1]);

	}

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

		f[maxn]=b1*t;

	}

	p=0;store=((ll)1<<60);

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

		while (2*xx[p+1]<=2*xx[b1]-t){

			store=min(store,f[p]-2*xx[p+1]);

			p++;

		}

		f[b1]=min(2*xx[b1]+store,f[p]+t);

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

	}

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

	

}
// 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: 17.796025318130503x):
#include<cmath>

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=100000+10;

ll f[maxn],xx[maxn];

ll n,e,t;

ll store;//fj-2xj+1

int main(){

	ll b1,b2,b3,b4;

	ll p;//定位

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

	

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

		scanf("%lld",&xx[b1]);

	}

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

		f[maxn]=b1*t;

	}

	p=0;store=((ll)1<<60);

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

		while (2*xx[p+1]<=2*xx[b1]-t){

			store=min(store,f[p]-2*xx[p+1]);

			p++;

		}

		f[b1]=min(2*xx[b1]+store,f[p]+t);

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

	}

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

	

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

using namespace std;

const int maxn=1e5+5;

const long long inf=1LL<<61;

typedef long long LL;

struct sgt{

	LL mn[maxn*2];

	int id(int l,int r){return l+r|l!=r;}



	void build(int l,int r){

		mn[id(l,r)]=inf;

		if(l==r)return ;

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

		build(l,mid);

		build(mid+1,r);

	}

	LL Q(int l,int r,int l0,int r0){

		if(l0<=l&&r0>=r)

			return mn[id(l,r)];

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

		LL ans=inf;

		if(l0<=mid)ans=min(ans,Q(l,mid,l0,r0));

		if(r0>mid)ans=min(ans,Q(mid+1,r,l0,r0));

		return ans;

	}

	void C(int l,int r,int ps,LL val){

		if(l==r){

			mn[id(l,r)]=val;

			return ;

		}

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

		if(ps<=mid)C(l,mid,ps,val);

		else C(mid+1,r,ps,val);

		mn[id(l,r)]=min(mn[id(l,mid)],mn[id(mid+1,r)]);

	}

}T1,T2;

int n;

LL T,E;

LL d[maxn];

LL dp[maxn],d2[maxn];



LL bf(){



	dp[1]=0;

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

		dp[i]=inf;

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

			dp[i]=min(dp[i],dp[j-1]+d[i]-d[j-1]+max(T,2*(d[i]-d[j])));

		}

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

	}





	LL ans=dp[n]+E-d[n];



	return ans;

}



int main(){

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

	n++;

	d[1]=0;

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

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

		d2[i]=d[i]*2;

	}





	//TODO

//	cout<< bf() <<endl;

//	return 0;

	T1.build(1,n);

	T2.build(1,n);





	dp[1]=0;

	T1.C(1,n,1,0);

	T2.C(1,n,1,0);



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



		dp[i]=dp[i-1]+d[i]-d[i-1]+T;





		auto bin=[&](int lef,int rig){

			int l=1,r=rig-1;



			while(l<r){

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

				if(2*(d[rig]-d[mid])>=T)

					l=mid+1;

				else

					r=mid;

			}



			int ans=0;

			for(int delta=-10;delta<=10;delta++){

				int ps=delta+l;

				if(1<=ps&&ps<rig){

					if(2*(d[rig]-d[ps])>=T){

						ans=ps;

					}else{

						break;

					}

				}

			}



			return ans;

		};

		int ps=bin(1,i);

		/*

		int ps=0;

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

			if(2*(d[i]-d[j])>=T){

				ps=j;

			}else{

				break;

			}

		}

*/

//		cerr<<ps<<" "<<bin(1,i)<<endl; 

//		assert(bin(1,i)==ps);



		//assert(ps==bin(1,i));



//		cerr<<"it is "<<i<<" "<<ps<<endl;

		LL res1=inf,res2=inf;



		if(ps>=1)

			res1=T1.Q(1,n,1,ps)+3*d[i];



		if(ps+1<=i-1)

			res2=T2.Q(1,n,ps+1,i-1)+d[i]+T;

//		cerr<<res1<<" "<<res2<<endl;



		dp[i]=min(dp[i],res1);

		dp[i]=min(dp[i],res2);

//		cerr<<"dp = "<<dp[i]<<endl;

		T1.C(1,n,i,dp[i-1]-d[i-1]-2*d[i]);

		T2.C(1,n,i,dp[i-1]-d[i-1]);

	}



	LL ans=dp[n]+E-d[n];



	cout<<ans<<endl;

	return 0;

}

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

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=100000+10;

ll f[maxn],xx[maxn];

ll n,e,t;

ll store;//fj-2xj+1

int main(){

	ll b1,b2,b3,b4;

	ll p;//定位

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

	

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

		scanf("%lld",&xx[b1]);

	}

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

		f[maxn]=b1*t;

	}

	p=0;store=((ll)1<<60);

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

		while (2*xx[p+1]<=2*xx[b1]-t){

			store=min(store,f[p]-2*xx[p+1]);

			p++;

		}

		f[b1]=min(2*xx[b1]+store,f[p]+t);

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

	}

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

	

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

using namespace std;

const int maxn=1e5+5;

const long long inf=1LL<<61;

typedef long long LL;

struct sgt{

	LL mn[maxn*2];

	int id(int l,int r){return l+r|l!=r;}



	void build(int l,int r){

		mn[id(l,r)]=inf;

		if(l==r)return ;

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

		build(l,mid);

		build(mid+1,r);

	}

	LL Q(int l,int r,int l0,int r0){

		if(l0<=l&&r0>=r)

			return mn[id(l,r)];

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

		LL ans=inf;

		if(l0<=mid)ans=min(ans,Q(l,mid,l0,r0));

		if(r0>mid)ans=min(ans,Q(mid+1,r,l0,r0));

		return ans;

	}

	void C(int l,int r,int ps,LL val){

		if(l==r){

			mn[id(l,r)]=val;

			return ;

		}

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

		if(ps<=mid)C(l,mid,ps,val);

		else C(mid+1,r,ps,val);

		mn[id(l,r)]=min(mn[id(l,mid)],mn[id(mid+1,r)]);

	}

}T1,T2;

int n;

LL T,E;

LL d[maxn];

LL dp[maxn],d2[maxn];



LL bf(){



	dp[1]=0;

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

		dp[i]=inf;

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

			dp[i]=min(dp[i],dp[j-1]+d[i]-d[j-1]+max(T,2*(d[i]-d[j])));

		}

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

	}





	LL ans=dp[n]+E-d[n];



	return ans;

}



int main(){

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

	n++;

	d[1]=0;

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

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

		d2[i]=d[i]*2;

	}





	//TODO

//	cout<< bf() <<endl;

//	return 0;

	T1.build(1,n);

	T2.build(1,n);





	dp[1]=0;

	T1.C(1,n,1,0);

	T2.C(1,n,1,0);



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



		dp[i]=dp[i-1]+d[i]-d[i-1]+T;





		auto bin=[&](int lef,int rig){

			int l=1,r=rig-1;



			while(l<r){

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

				if(2*(d[rig]-d[mid])>=T)

					l=mid+1;

				else

					r=mid;

			}



			int ans=0;

			for(int delta=-5;delta<=5;delta++){

				int ps=delta+l;

				if(1<=ps&&ps<rig){

					if(2*(d[rig]-d[ps])>=T){

						ans=ps;

					}else{

						break;

					}

				}

			}



			return ans;

		};

		int ps=bin(1,i);

		/*

		int ps=0;

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

			if(2*(d[i]-d[j])>=T){

				ps=j;

			}else{

				break;

			}

		}

*/

//		cerr<<ps<<" "<<bin(1,i)<<endl; 

//		assert(bin(1,i)==ps);



		//assert(ps==bin(1,i));



//		cerr<<"it is "<<i<<" "<<ps<<endl;

		LL res1=inf,res2=inf;



		if(ps>=1)

			res1=T1.Q(1,n,1,ps)+3*d[i];



		if(ps+1<=i-1)

			res2=T2.Q(1,n,ps+1,i-1)+d[i]+T;

//		cerr<<res1<<" "<<res2<<endl;



		dp[i]=min(dp[i],res1);

		dp[i]=min(dp[i],res2);

//		cerr<<"dp = "<<dp[i]<<endl;

		T1.C(1,n,i,dp[i-1]-d[i-1]-2*d[i]);

		T2.C(1,n,i,dp[i-1]-d[i-1]);

	}



	LL ans=dp[n]+E-d[n];



	cout<<ans<<endl;

	return 0;

}

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

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=100000+10;

ll f[maxn],xx[maxn];

ll n,e,t;

ll store;//fj-2xj+1

int main(){

	ll b1,b2,b3,b4;

	ll p;//定位

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

	

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

		scanf("%lld",&xx[b1]);

	}

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

		f[maxn]=b1*t;

	}

	p=0;store=((ll)1<<60);

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

		while (2*xx[p+1]<=2*xx[b1]-t){

			store=min(store,f[p]-2*xx[p+1]);

			p++;

		}

		f[b1]=min(2*xx[b1]+store,f[p]+t);

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

	}

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

	

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

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=100000+10;

ll f[maxn],xx[maxn];

ll n,e,t;

ll store;//fj-2xj+1

int main(){

	ll b1,b2,b3,b4;

	ll p;//定位

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

	

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

		scanf("%lld",&xx[b1]);

	}

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

		f[maxn]=b1*t;

	}

	p=0;store=((ll)1<<60);

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

		while (2*xx[p+1]<=2*xx[b1]-t){

			store=min(store,f[p]-2*xx[p+1]);

			p++;

		}

		f[b1]=min(2*xx[b1]+store,f[p]+t);

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

	}

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

	

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

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=100000+10;

ll f[maxn],xx[maxn];

ll n,e,t;

ll store;//fj-2xj+1

int main(){

	ll b1,b2,b3,b4;

	ll p;//定位

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

	

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

		scanf("%lld",&xx[b1]);

	}

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

		f[maxn]=b1*t;

	}

	p=0;store=((ll)1<<60);

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

		while (2*xx[p+1]<=2*xx[b1]-t){

			store=min(store,f[p]-2*xx[p+1]);

			p++;

		}

		f[b1]=min(2*xx[b1]+store,f[p]+t);

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

	}

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

	

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

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=100000+10;

ll f[maxn],xx[maxn];

ll n,e,t;

ll store;//fj-2xj+1

int main(){

	ll b1,b2,b3,b4;

	ll p;//定位

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

	

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

		scanf("%lld",&xx[b1]);

	}

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

		f[maxn]=b1*t;

	}

	p=0;store=((ll)1<<60);

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

		while (2*xx[p+1]<=2*xx[b1]-t){

			store=min(store,f[p]-2*xx[p+1]);

			p++;

		}

		f[b1]=min(2*xx[b1]+store,f[p]+t);

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

	}

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

	

}