stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef long double DD;

const int inf = 1e9;

const int mo= 1e9+7;

const int N = 101010;

int n;

LL T, E, f[N], p[N];



struct sta{

	LL f,d;

	sta(){}

	sta(LL x, LL y){

		f = x;

		d = y;

	}

	friend bool operator <(sta a, sta b){

		if(a.f == b.f)

			return a.d<b.d;

		else 

			return a.f < b.f;

	}

};

set<sta> s1,s2;



int main(){

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

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

		scanf("%lld", p + i);

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

	s1.insert(sta(T, p[1]));

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

		while(!s1.empty() && (p[i] - (*s1.begin()).d) * 2 > T){

			sta t = *s1.begin();

			s1.erase(s1.begin());

			s2.insert( sta(t.f - T - t.d * 2, t.d) );

		}

		f[i]=1ll << 62;

		if(!s2.empty())

			f[i]=(*s2.begin()).f + p[i] * 3;

		if(!s1.empty())

			f[i] = min(f[i], (*s1.begin()).f + p[i]);

		s1.insert(sta(f[i] - p[i] + T, p[i + 1]));

	}

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

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

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

	return 0;

}






// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

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

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

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

    }

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

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <algorithm>

using namespace std;

inline int read()

{

	int res, ok = 1;

	char ch;

	for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())

	if (ch == '-')

	ok = -1;

	res = ch - '0';

	for (ch = getchar(); ch >= '0' && ch <= '9'; ch = getchar())

	res = res * 10 + ch - '0';

	return res * ok;

}

int n, t, e, a[100005], last;

long long ans[100005], minn = 1LL << 60;

int main()

{

	n = read();

	e = read();

	t = read();

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

	a[i] = read();

	ans[0] = 0;

	ans[1] = t;

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

	{

		while (2LL * (a[i] - a[last + 1]) > t)

		{

			long long now = ans[last] - 2LL * a[last + 1];

			minn = min (minn, now);

			last++;

		}

		ans[i] = ans[i - 1] + t;

		if (last > 0)

		ans[i] = min (ans[i], minn + 2LL * a[i]);

		ans[i] = min (ans[i], ans[last] + t);

	}

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

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

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

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

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

    }

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

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;



#define lowbit(a) (a&-a)

typedef long long ll;

const int maxn = 100010; const ll inf = 1LL<<60;

int N,T,E,X[maxn]; ll tree1[4*maxn],tree2[4*maxn],f[maxn];



inline int gi()

{

	char ch; int ret = 0,f = 1;

	do ch = getchar(); while (!(ch >= '0'&&ch <= '9')&&ch != '-');

	if (ch == '-') f = -1,ch = getchar();

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

	return ret*f;

}



inline void build(int now,int l,int r)

{

	tree1[now] = tree2[now] = inf;

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

	build(now<<1,l,mid); build(now<<1|1,mid+1,r);

}



inline void modify(ll *tree,int now,int l,int r,int pos,ll key)

{

	if (l == r) { tree[now] = key; return; } int mid = (l+r)>>1;

	if (pos <= mid) modify(tree,now<<1,l,mid,pos,key);

	else modify(tree,now<<1|1,mid+1,r,pos,key);

	tree[now] = min(tree[now<<1],tree[now<<1|1]);

}



inline ll query(ll *tree,int now,int l,int r,int ql,int qr)

{

	if (ql == l&&qr == r) return tree[now]; int mid = (l+r)>>1;

	if (qr <= mid) return query(tree,now<<1,l,mid,ql,qr);

	else if (ql > mid) return query(tree,now<<1|1,mid+1,r,ql,qr);

	else return min(query(tree,now<<1,l,mid,ql,mid),query(tree,now<<1|1,mid+1,r,mid+1,qr));

}



int main()

{

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

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

	N = gi(); E = gi(); T = gi();

	for (int i = 1;i <= N;++i) X[i] = gi(),tree1[i] = tree2[i] = 1LL<<60;

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

	{

		modify(tree1,1,1,N,i,f[i-1]-2LL*(ll)X[i]-(ll)X[i-1]);

		modify(tree2,1,1,N,i,f[i-1]-(ll)X[i-1]);

		int l = 0,r = i-1,mid; f[i] = inf;

		while (l <= r)

		{

			mid = (l+r)>>1;

			if (T-2LL*(X[i]-X[mid+1]) > 0) r = mid-1;

			else l = mid+1;

		}

		if (r+1) f[i] = query(tree1,1,1,N,1,r+1)+3LL*X[i];

		if (r+2 <= i) f[i] = min(f[i],query(tree2,1,1,N,r+2,i)+(ll)X[i]+(ll)T);

	}

	cout << f[N]+(ll)E-(ll)X[N] << endl;

	return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

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

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

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

    }

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

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;

typedef long long ll;



const int MAXN = 100005;



int n, e, T;

int x[MAXN];



void input()

{

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

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

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

}



ll f[MAXN];



void solve()

{

	f[0] = 0;

	ll minv = 1e18;

	int j = 0;

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

	{

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

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

		{

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

			j++;

		}

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

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

	}

}



void output()

{

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

}



int main()

{

	input();

	solve();

	output();



	return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

using namespace std;



typedef long long ll;



const int maxn =  1e5 + 5;



int n, E, T, pos;

int a[maxn];

ll f[maxn], mn = 1e18;



int main()

{

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

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

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

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

    {

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

        {

            mn = min(mn, f[pos] - 2 * a[pos + 1]);

            pos++;

        }

        f[i] = min(f[i - 1] + T, mn + 2 * a[i]);

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

    }

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

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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);

    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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]);

}

// Optimized solution to the same problem (faster):
#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);

    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
    #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];

    }

// Optimized solution to the same problem (faster):
#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);

    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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);

    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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);

    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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);

    }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
/* --- 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:

*/

// Optimized solution to the same problem (faster):
#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);

    }

}


// Fastest known solution for this problem: