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

#include <iostream>

#include <algorithm>

#include <cstring>

#include <set>

#define N 100010

#define LL long long

using namespace std;

int n, e, t;

int x[N];

LL dp[N];

multiset<LL> st1;

multiset<LL> st2;



int main() {

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

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

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

	}

	

	dp[0] = 0;

	x[0] = 0;

	int last = 0;

	st1.insert(- 2LL * x[1]);

	st2.insert(t);

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

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

			st1.insert(dp[last] - x[last] - 2LL * x[last + 1]);

			st2.erase(st2.find(dp[last] - x[last] + t));

			++last;

		}

		if (last - 1 >= 0) dp[i] = min(*st1.begin() + 3LL * x[i], *st2.begin() + x[i]);

		else dp[i] = *st2.begin() + x[i];

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

//cout << dp[i] << ' ';

	}

//cout << endl;

	

	cout << dp[n] + e - x[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.513732805054067x):
#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <set>

#define N 100010

#define LL long long

using namespace std;

int n, e, t;

int x[N];

LL dp[N];

multiset<LL> st1;

multiset<LL> st2;



int main() {

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

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

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

	}

	

	dp[0] = 0;

	x[0] = 0;

	int last = 0;

	st1.insert(- 2LL * x[1]);

	st2.insert(t);

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

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

			st1.insert(dp[last] - x[last] - 2LL * x[last + 1]);

			st2.erase(st2.find(dp[last] - x[last] + t));

			++last;

		}

		if (last - 1 >= 0) dp[i] = min(*st1.begin() + 3LL * x[i], *st2.begin() + x[i]);

		else dp[i] = *st2.begin() + x[i];

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

//cout << dp[i] << ' ';

	}

//cout << endl;

	

	cout << dp[n] + e - x[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.394984640257779x):
#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <set>

#define N 100010

#define LL long long

using namespace std;

int n, e, t;

int x[N];

LL dp[N];

multiset<LL> st1;

multiset<LL> st2;



int main() {

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

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

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

	}

	

	dp[0] = 0;

	x[0] = 0;

	int last = 0;

	st1.insert(- 2LL * x[1]);

	st2.insert(t);

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

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

			st1.insert(dp[last] - x[last] - 2LL * x[last + 1]);

			st2.erase(st2.find(dp[last] - x[last] + t));

			++last;

		}

		if (last - 1 >= 0) dp[i] = min(*st1.begin() + 3LL * x[i], *st2.begin() + x[i]);

		else dp[i] = *st2.begin() + x[i];

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

//cout << dp[i] << ' ';

	}

//cout << endl;

	

	cout << dp[n] + e - x[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.8271104168218821x):
#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <queue>

#include <vector>

#include <map>

#include <bitset>

using namespace std;



#define N 100010

typedef long long ll;



const ll INF=1e18;



int n,E,T;

int dis[N];

ll Dp[N];





inline int read()

{

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

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

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

    return x*f;

}



int main()

{

    n=read();E=read();T=read();

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

        dis[i]=read();

    Dp[0]=0;

    int pos=0;ll Min=INF;

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

    {

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

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

        {

            Min=min(Min,Dp[pos]-2*dis[pos+1]);

            pos++;

        }

        Dp[i]=min(min(Dp[i],Dp[pos]+T),Min+2*dis[i]);

    }

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

    return 0;

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

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <queue>

#include <vector>

#include <map>

#include <bitset>

using namespace std;



#define N 100010

typedef long long ll;



const ll INF=1e18;



int n,E,T;

int dis[N];

ll Dp[N];





inline int read()

{

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

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

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

    return x*f;

}



int main()

{

    n=read();E=read();T=read();

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

        dis[i]=read();

    Dp[0]=0;

    int pos=0;ll Min=INF;

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

    {

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

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

        {

            Min=min(Min,Dp[pos]-2*dis[pos+1]);

            pos++;

        }

        Dp[i]=min(min(Dp[i],Dp[pos]+T),Min+2*dis[i]);

    }

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

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

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <queue>

#include <vector>

#include <map>

#include <bitset>

using namespace std;



#define N 100010

typedef long long ll;



const ll INF=1e18;



int n,E,T;

int dis[N];

ll Dp[N];





inline int read()

{

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

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

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

    return x*f;

}



int main()

{

    n=read();E=read();T=read();

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

        dis[i]=read();

    Dp[0]=0;

    int pos=0;ll Min=INF;

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

    {

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

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

        {

            Min=min(Min,Dp[pos]-2*dis[pos+1]);

            pos++;

        }

        Dp[i]=min(min(Dp[i],Dp[pos]+T),Min+2*dis[i]);

    }

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

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

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <queue>

#include <vector>

#include <map>

#include <bitset>

using namespace std;



#define N 100010

typedef long long ll;



const ll INF=1e18;



int n,E,T;

int dis[N];

ll Dp[N];





inline int read()

{

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

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

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

    return x*f;

}



int main()

{

    n=read();E=read();T=read();

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

        dis[i]=read();

    Dp[0]=0;

    int pos=0;ll Min=INF;

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

    {

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

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

        {

            Min=min(Min,Dp[pos]-2*dis[pos+1]);

            pos++;

        }

        Dp[i]=min(min(Dp[i],Dp[pos]+T),Min+2*dis[i]);

    }

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

    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.823687727872883x):
/* --- 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:

*/
// 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.4370601307876956x):
/* --- 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:

*/