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

#include<cstring>

#include<algorithm>

using namespace std;

const int N=100005;

typedef long long ll;

const ll INF=1e15;

ll d[N];

int n,m,T;

ll a[N];

int q[N];

int s,t;

int main()

{

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

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

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

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

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

        d[i]=INF;

    }

    if(n<=1000){

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

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

                ll f=max(a[i]-a[j+1],T-(a[i]-a[j+1]));

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

            }

        ll ans=d[n]+m-a[n];

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

    }

    else{

        s=1,t=1;

        ll z=INF;

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

            while(s<=t&&2*(a[i]-a[q[s]+1])>T){

                z=min(z,d[q[s]]-a[q[s]]-2*a[q[s]+1]);

                s++;

            }

            d[i]=min(d[i],a[i]+z+2*a[i]);

            //d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+2*(a[i]-a[q[s]+1]));

            d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+T);

            while(s<=t&&d[q[s]]-a[q[s]]>=d[i]-a[i])

                t--;

            q[++t]=i;

        }

        ll ans=d[n]+m-a[n];

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

    }

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

using namespace std;

long long f[112345];

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

int main(){

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

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

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

	pp = 1;

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

	f[0] = 0;

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

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

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

			pp++;

		}

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

	}

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

}

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

#include<cstring>

#include<algorithm>

using namespace std;

const int N=100005;

typedef long long ll;

const ll INF=1e15;

ll d[N];

int n,m,T;

ll a[N];

int q[N];

int s,t;

int main()

{

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

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

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

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

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

        d[i]=INF;

    }

    if(n<=1000){

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

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

                ll f=max(a[i]-a[j+1],T-(a[i]-a[j+1]));

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

            }

        ll ans=d[n]+m-a[n];

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

    }

    else{

        s=1,t=1;

        ll z=INF;

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

            while(s<=t&&2*(a[i]-a[q[s]+1])>T){

                z=min(z,d[q[s]]-a[q[s]]-2*a[q[s]+1]);

                s++;

            }

            d[i]=min(d[i],a[i]+z+2*a[i]);

            //d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+2*(a[i]-a[q[s]+1]));

            d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+T);

            while(s<=t&&d[q[s]]-a[q[s]]>=d[i]-a[i])

                t--;

            q[++t]=i;

        }

        ll ans=d[n]+m-a[n];

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

    }

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

    using namespace std;

    const int MAX = (1e5)+1;

     

    int n;

    long long E, T, x[MAX], dp[MAX], f[MAX];

    multiset<long long> l, m;

    int main() {

    	ios::sync_with_stdio(false);

    	cin.tie(0);

    	cin >> n >> E >> T;

    	l.insert(f[0] = T);

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

    		cin >> x[i];

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

    			l.erase(l.find(f[j]));

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

    			m.insert(f[j]);

    			j++;

    		}

    		dp[i] = LLONG_MAX;

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

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

    		l.insert(f[i] = dp[i]-x[i]+T);

    	}

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

    }

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

#include<cstring>

#include<algorithm>

using namespace std;

const int N=100005;

typedef long long ll;

const ll INF=1e15;

ll d[N];

int n,m,T;

ll a[N];

int q[N];

int s,t;

int main()

{

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

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

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

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

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

        d[i]=INF;

    }

    if(n<=1000){

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

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

                ll f=max(a[i]-a[j+1],T-(a[i]-a[j+1]));

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

            }

        ll ans=d[n]+m-a[n];

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

    }

    else{

        s=1,t=1;

        ll z=INF;

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

            while(s<=t&&2*(a[i]-a[q[s]+1])>T){

                z=min(z,d[q[s]]-a[q[s]]-2*a[q[s]+1]);

                s++;

            }

            d[i]=min(d[i],a[i]+z+2*a[i]);

            //d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+2*(a[i]-a[q[s]+1]));

            d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+T);

            while(s<=t&&d[q[s]]-a[q[s]]>=d[i]-a[i])

                t--;

            q[++t]=i;

        }

        ll ans=d[n]+m-a[n];

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

    }

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



using namespace std;



typedef long long LL;



const LL INF = 1e18;

const int N = 100010;



LL f[N];



int x[N];

int n, T, E;



int main() {

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

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

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

	}

	int p = 0;

	LL mn = INF;

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

		f[i] = INF;

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

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

			++p;

		}

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

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

	}

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

	return 0;

}

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

#include<cstring>

#include<algorithm>

using namespace std;

const int N=100005;

typedef long long ll;

const ll INF=1e15;

ll d[N];

int n,m,T;

ll a[N];

int q[N];

int s,t;

int main()

{

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

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

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

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

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

        d[i]=INF;

    }

    if(n<=1000){

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

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

                ll f=max(a[i]-a[j+1],T-(a[i]-a[j+1]));

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

            }

        ll ans=d[n]+m-a[n];

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

    }

    else{

        s=1,t=1;

        ll z=INF;

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

            while(s<=t&&2*(a[i]-a[q[s]+1])>T){

                z=min(z,d[q[s]]-a[q[s]]-2*a[q[s]+1]);

                s++;

            }

            d[i]=min(d[i],a[i]+z+2*a[i]);

            //d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+2*(a[i]-a[q[s]+1]));

            d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+T);

            while(s<=t&&d[q[s]]-a[q[s]]>=d[i]-a[i])

                t--;

            q[++t]=i;

        }

        ll ans=d[n]+m-a[n];

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

    }

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

}

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

#include<cstring>

#include<algorithm>

using namespace std;

const int N=100005;

typedef long long ll;

const ll INF=1e15;

ll d[N];

int n,m,T;

ll a[N];

int q[N];

int s,t;

int main()

{

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

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

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

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

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

        d[i]=INF;

    }

    if(n<=1000){

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

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

                ll f=max(a[i]-a[j+1],T-(a[i]-a[j+1]));

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

            }

        ll ans=d[n]+m-a[n];

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

    }

    else{

        s=1,t=1;

        ll z=INF;

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

            while(s<=t&&2*(a[i]-a[q[s]+1])>T){

                z=min(z,d[q[s]]-a[q[s]]-2*a[q[s]+1]);

                s++;

            }

            d[i]=min(d[i],a[i]+z+2*a[i]);

            //d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+2*(a[i]-a[q[s]+1]));

            d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+T);

            while(s<=t&&d[q[s]]-a[q[s]]>=d[i]-a[i])

                t--;

            q[++t]=i;

        }

        ll ans=d[n]+m-a[n];

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

    }

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

}


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

#include<cstring>

#include<algorithm>

using namespace std;

const int N=100005;

typedef long long ll;

const ll INF=1e15;

ll d[N];

int n,m,T;

ll a[N];

int q[N];

int s,t;

int main()

{

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

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

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

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

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

        d[i]=INF;

    }

    if(n<=1000){

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

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

                ll f=max(a[i]-a[j+1],T-(a[i]-a[j+1]));

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

            }

        ll ans=d[n]+m-a[n];

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

    }

    else{

        s=1,t=1;

        ll z=INF;

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

            while(s<=t&&2*(a[i]-a[q[s]+1])>T){

                z=min(z,d[q[s]]-a[q[s]]-2*a[q[s]+1]);

                s++;

            }

            d[i]=min(d[i],a[i]+z+2*a[i]);

            //d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+2*(a[i]-a[q[s]+1]));

            d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+T);

            while(s<=t&&d[q[s]]-a[q[s]]>=d[i]-a[i])

                t--;

            q[++t]=i;

        }

        ll ans=d[n]+m-a[n];

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

    }

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

#include<cstring>

#include<algorithm>

using namespace std;

const int N=100005;

typedef long long ll;

const ll INF=1e15;

ll d[N];

int n,m,T;

ll a[N];

int q[N];

int s,t;

int main()

{

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

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

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

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

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

        d[i]=INF;

    }

    if(n<=1000){

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

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

                ll f=max(a[i]-a[j+1],T-(a[i]-a[j+1]));

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

            }

        ll ans=d[n]+m-a[n];

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

    }

    else{

        s=1,t=1;

        ll z=INF;

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

            while(s<=t&&2*(a[i]-a[q[s]+1])>T){

                z=min(z,d[q[s]]-a[q[s]]-2*a[q[s]+1]);

                s++;

            }

            d[i]=min(d[i],a[i]+z+2*a[i]);

            //d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+2*(a[i]-a[q[s]+1]));

            d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+T);

            while(s<=t&&d[q[s]]-a[q[s]]>=d[i]-a[i])

                t--;

            q[++t]=i;

        }

        ll ans=d[n]+m-a[n];

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

    }

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

#include <iostream>

#include <cstring>

#include <string>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <utility>

#include <map>

#include <stack>

#include <set>

#include <vector>

#include <queue>

#include <deque>

#include <sstream>

#define x first

#define y second

#define mp make_pair

#define pb push_back

#define LL long long

#define LB long double

#define Pair pair<int,int>

#define LOWBIT(x) x & (-x)

using namespace std;



const int MOD=1e9+7;

const double eps=1e-10;

const int INF=2e9;

const LL LINF=2e16;

const int magic=100;



inline int getint()

{

	char ch;

	while ((ch=getchar())<'0' || ch>'9') {}

	int res=ch-'0';

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

	return res;

}



int n,e,T;

LL a[100048];

priority_queue<pair<LL,int> > q1,q2;

LL dp[100048];



int main ()

{

	int i;

	n=getint();e=getint();T=getint();

	for (i=1;i<=n;i++) a[i]=(LL)getint();

	dp[0]=0;

	a[0]=0;

	q2.push(mp(a[0]-dp[0],0));

	//dp[1]=a[1]+T;

	//q2.push(mp(a[1]-dp[1],1));

	int num1,num2;

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

	{

		

		bool f=true;

		while (!q2.empty() && f)

		{

			int num=q2.top().y;f=false;

			if (T-2*a[i]+2*a[num+1]<0)

			{

				q2.pop();f=true;

				q1.push(mp(a[num]+2*a[num+1]-dp[num],num));

			}

		}

		LL ans1=LINF,ans2=LINF;

		if (!q1.empty())

		{

			num1=q1.top().y;

			ans1=dp[num1]+3*a[i]-a[num1]-2*a[num1+1];

		}

		if (!q2.empty())

		{

			num2=q2.top().y;

			ans2=dp[num2]+a[i]-a[num2]+T;

		}

		dp[i]=min(ans1,ans2);

		q2.push(mp(a[i]-dp[i],i));

	}

	//for (i=1;i<=n;i++) cout<<dp[i]<<' ';

	//cout<<endl;

	cout<<dp[n]+(e-a[n])<<endl;

	return 0;

}

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

#include<cstring>

#include<algorithm>

using namespace std;

const int N=100005;

typedef long long ll;

const ll INF=1e15;

ll d[N];

int n,m,T;

ll a[N];

int q[N];

int s,t;

int main()

{

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

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

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

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

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

        d[i]=INF;

    }

    if(n<=1000){

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

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

                ll f=max(a[i]-a[j+1],T-(a[i]-a[j+1]));

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

            }

        ll ans=d[n]+m-a[n];

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

    }

    else{

        s=1,t=1;

        ll z=INF;

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

            while(s<=t&&2*(a[i]-a[q[s]+1])>T){

                z=min(z,d[q[s]]-a[q[s]]-2*a[q[s]+1]);

                s++;

            }

            d[i]=min(d[i],a[i]+z+2*a[i]);

            //d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+2*(a[i]-a[q[s]+1]));

            d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+T);

            while(s<=t&&d[q[s]]-a[q[s]]>=d[i]-a[i])

                t--;

            q[++t]=i;

        }

        ll ans=d[n]+m-a[n];

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

    }

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

#include <fstream>

#include <cstdio>

#include <algorithm>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <utility>

#include <map>

#include <set>

#include <cmath>

#include <cstdlib>

#include <ctime>

#include <functional>

#include <sstream>

#include <cstring>

#include <bitset>

#include <stack>

using namespace std;

#define MP make_pair

#define PB push_back

const int INF=1e9;



int n,e,t,pos;

long long a[100005];

long long dp[100005],cur;



int main()

{

	cin>>n>>e>>t;

	for (int i=1;i<=n;i++) cin>>a[i];

	dp[0]=0;

	cur=1e18;

	pos=0;

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

	{

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

		{

			cur=min(cur,dp[pos]-2*a[pos+1]);

			pos++;

		}

		dp[i]=min(cur+2*a[i],dp[pos]+t);

	}

	cout<<dp[n]+e;

	return 0;

}

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

#include<cstring>

#include<algorithm>

using namespace std;

const int N=100005;

typedef long long ll;

const ll INF=1e15;

ll d[N];

int n,m,T;

ll a[N];

int q[N];

int s,t;

int main()

{

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

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

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

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

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

        d[i]=INF;

    }

    if(n<=1000){

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

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

                ll f=max(a[i]-a[j+1],T-(a[i]-a[j+1]));

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

            }

        ll ans=d[n]+m-a[n];

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

    }

    else{

        s=1,t=1;

        ll z=INF;

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

            while(s<=t&&2*(a[i]-a[q[s]+1])>T){

                z=min(z,d[q[s]]-a[q[s]]-2*a[q[s]+1]);

                s++;

            }

            d[i]=min(d[i],a[i]+z+2*a[i]);

            //d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+2*(a[i]-a[q[s]+1]));

            d[i]=min(d[i],d[q[s]]+a[i]-a[q[s]]+T);

            while(s<=t&&d[q[s]]-a[q[s]]>=d[i]-a[i])

                t--;

            q[++t]=i;

        }

        ll ans=d[n]+m-a[n];

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

    }

}
// 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.822719109012568x):
#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;

}