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

#include<cstdio>

#include<cstring>

#include<cmath>



using namespace std;

const int N=1000005;

const int MOD=998244353;

typedef long long LL;



int n,m,fac[N],inv[N];

int Ans1,Ans2;



//LL gcd(LL x,LL y) {

//	if(!y) return x;

//	return gcd(y,x%y);

//}

//

//struct Data{

//	LL x,y;

//	Data(LL _x=0,LL _y=0) {x=_x; y=_y;}

//	friend Data operator+(const Data A,const Data B){

//		Data ret; ret.y=A.y*B.y; ret.x=A.x*B.y+A.y*B.x;

//		LL tmp=gcd(ret.x,ret.y); ret.x/=tmp; ret.y/=tmp;

//		return ret;

//	}

//	friend Data operator*(const Data A,const Data B){

//		Data ret; ret.x=A.x*B.x; ret.y=A.y*B.y;

//		LL tmp=gcd(ret.x,ret.y); ret.x/=tmp; ret.y/=tmp;

//		return ret;

//	}

//}ans;



inline int fast_pow(int x,int y){

	int ret=1;

	for(;y;y>>=1){

		if(y&1) ret=(LL)ret*x%MOD;

		x=(LL)x*x%MOD;

	}

	return ret;

}



inline int C(int x,int y){

	return (LL)fac[x]*inv[y]%MOD*inv[x-y]%MOD;

}



int main(){

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

	if(n>m) swap(n,m); fac[0]=inv[0]=1;

	int i;

	for(i=1;i<=n+m;i+=4){

		fac[i]=1ll*fac[i-1]*i%MOD;

		fac[i+1]=1ll*fac[i]*(i+1)%MOD;

		fac[i+2]=1ll*fac[i+1]*(i+2)%MOD;

		fac[i+3]=1ll*fac[i+2]*(i+3)%MOD;

	}

	for(;i<=n+m;i++) fac[i]=fac[i-1]*i%MOD;

	inv[n+m]=fast_pow(fac[n+m],MOD-2);

	for(int i=n+m-1;~i;i--) inv[i]=1ll*inv[i+1]*(i+1)%MOD;

	Ans1=1ll*2*m*C(n+m,n)%MOD; Ans2=fast_pow(C(n+m,n)*2%MOD,MOD-2);

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

		Ans1=Ans1+1ll*C(n-i+m-i,n-i)*C(i+i,i)%MOD;	

		Ans1%=MOD;

	}

	printf("%lld\n",1ll*Ans1*Ans2%MOD);

//	ans=ans+Data(1,2)*Data(C(n-i+m-i,n-i)*C(i+i,i),C(n+m,n));

//	printf("%lld\n",1ll*ans.x*fast_pow(ans.y,MOD-2)%MOD);

	return 0;	

}

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



const int mod=998244353,N=1000005;



int fexp(int a,int b)

{

	int x=1;

	for(;b;b>>=1,a=1LL*a*a%mod)

		if(b&1)x=1LL*x*a%mod;

	return x;

}



int n,m,ans,fac[N],ifac[N];



int main()

{

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

	n+=m;

	fac[0]=1;

	for(int i=1; i<=n; ++i)fac[i]=1LL*i*fac[i-1]%mod;

	ifac[n]=fexp(fac[n],mod-2);

	for(int i=n-1; ~i; --i)ifac[i]=1LL*(i+1)*ifac[i+1]%mod;

	n-=m;

	if(n<m){int k=n;n=m;m=k;}

	for(int x=1; x<=m; ++x)

		ans=(ans+1LL*fac[x+x]*ifac[x]%mod*ifac[x]%mod*fac[n-x+m-x]%mod*ifac[n-x]%mod*ifac[m-x])%mod;

	ans=1LL*ans*ifac[2]%mod*ifac[n+m]%mod*fac[n]%mod*fac[m]%mod;

	printf("%d",(ans+n)%mod);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

#define rep(i_, s_, t_) for (ll i_ = (s_); i_ <= (t_); ++i_)

#define re(i_, s_, t_) for (ll i_ = (s_); i_ < (t_); ++i_)

#define per(i_, s_, t_) for (ll i_ = (s_); i_ >= (t_); --i_)

typedef long long ll;

const ll P = 998244353, N = 1e6 + 5;

ll fac[N];

ll ans;

ll qpow(ll x, ll t = P - 2) {

	ll res = 1;

	for (; t; t >>= 1, x = 1LL * x * x % P)

		if (t & 1)

			res = 1LL * res * x % P;

	return res;

}

ll C(ll m, ll n) { return 1LL * fac[m] * qpow(fac[m - n]) % P * qpow(fac[n]) % P; }

int main() {

	ll n, m;

	scanf("%lld%lld", &n, &m);

	if (n > m)

		swap(n, m);

	fac[0] = fac[1] = 1;

	rep (i, 2, n + m)

		fac[i] = 1ll * fac[i - 1] * i % P;

	rep (i, 1, n)

		ans = (ans + C(n + m - 2 * i, n - i) * C(2 * i, i) % P) % P;

	ans = ans * fac[n] % P * fac[m] % P * qpow(fac[n + m]) % P * qpow(2) % P;

	printf("%lld\n", (m + ans) % P);

	return 0;

}

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



const int mod=998244353,N=1000005;



int fexp(int a,int b)

{

	int x=1;

	for(;b;b>>=1,a=1LL*a*a%mod)

		if(b&1)x=1LL*x*a%mod;

	return x;

}



int n,m,ans,fac[N],ifac[N];



int main()

{

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

	n+=m;

	fac[0]=1;

	for(int i=1; i<=n; ++i)fac[i]=1LL*i*fac[i-1]%mod;

	ifac[n]=fexp(fac[n],mod-2);

	for(int i=n-1; ~i; --i)ifac[i]=1LL*(i+1)*ifac[i+1]%mod;

	n-=m;

	if(n<m){int k=n;n=m;m=k;}

	for(int x=1; x<=m; ++x)

		ans=(ans+1LL*fac[x+x]*ifac[x]%mod*ifac[x]%mod*fac[n-x+m-x]%mod*ifac[n-x]%mod*ifac[m-x])%mod;

	ans=1LL*ans*ifac[2]%mod*ifac[n+m]%mod*fac[n]%mod*fac[m]%mod;

	printf("%d",(ans+n)%mod);

	return 0;

}


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

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

#include<unordered_map>

using namespace std;

#define ri register int

#define il inline

#define pb emplace_back

#define solid const auto &

#define enter putchar('\n')

#define Size(x) ((int)x.size())

#define mem(x,y) memset(x,y,sizeof(x))

#define gm int mid((l+r)>>1)

#define mp make_pair

#define fi first

#define se second

typedef long long LL;

typedef unsigned long long ull;

typedef pair<int,int> pii;

template<class T>il void in(T &x)

{

	x=0; char c=getchar(); bool f=0;

	while(!isdigit(c)) f|=(c=='-'),c=getchar();

	while(isdigit(c)) x=x*10+(c^'0'),c=getchar();

	f?x=-x:0;

}

template<class T>il void out(T x,const char c='\n')

{

	static short st[30]; short tp=0;

	if(x<0) putchar('-'),x=-x;

	do st[++tp]=x%10,x/=10; while(x);

	while(tp) putchar('0'|st[tp--]);

	putchar(c);

}

template<class T>il void err(const T &x,const char c='\n') {cerr<<x<<c;}

template<class T,class ...Args>il void err(const T &x,const Args &...args) {err(x,' '),err(args...);}

const int md=998244353;

il int qpow(int a,int b) {int r=1; for(; b; b>>=1,a=(LL)a*a%md) if(b&1) r=(LL)r*a%md; return r;}

il int fit(const int x) {return x>=md?x-md:x;}

namespace i207M

{

const int N=1000005;

int fac[N],ifac[N];

void prework(int n)

{

	fac[0]=1;

	for(ri i=1;i<=n;++i) fac[i]=(LL)fac[i-1]*i%md;

	ifac[n]=qpow(fac[n],md-2);

	for(ri i=n;i>=1;--i) ifac[i-1]=(LL)ifac[i]*i%md;

}

il int C(int n,int m) {return (LL)fac[n]*ifac[m]%md*ifac[n-m]%md;}

int n,m;

signed main()

{

#ifdef M207

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

#endif

	in(n),in(m);

	if(n>m) swap(n,m);

	prework(n+m);

	int ans=0;

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

		ans=(ans+(LL)C(2*i,i)*C(n-i+m-i,n-i))%md;

	ans=(LL)ans*qpow(C(n+m,n),md-2)%md*(md+1)/2%md;

	ans=fit(ans+m);

	out(ans);

	return 0;

}

}

signed main()

{

	i207M::main();

	return 0;

}


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



const int mod=998244353,N=1000005;



int fexp(int a,int b)

{

	int x=1;

	for(;b;b>>=1,a=1LL*a*a%mod)

		if(b&1)x=1LL*x*a%mod;

	return x;

}



int n,m,ans,fac[N],ifac[N];



int main()

{

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

	n+=m;

	fac[0]=1;

	for(int i=1; i<=n; ++i)fac[i]=1LL*i*fac[i-1]%mod;

	ifac[n]=fexp(fac[n],mod-2);

	for(int i=n-1; ~i; --i)ifac[i]=1LL*(i+1)*ifac[i+1]%mod;

	n-=m;

	if(n<m){int k=n;n=m;m=k;}

	for(int x=1; x<=m; ++x)

		ans=(ans+1LL*fac[x+x]*ifac[x]%mod*ifac[x]%mod*fac[n-x+m-x]%mod*ifac[n-x]%mod*ifac[m-x])%mod;

	ans=1LL*ans*ifac[2]%mod*ifac[n+m]%mod*fac[n]%mod*fac[m]%mod;

	printf("%d",(ans+n)%mod);

	return 0;

}


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

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 1000000

#define MOD 998244353

#define LL long long

int n,m;

int inv[MAXN+5],fac[MAXN+5];

int ans;

int fst_pow(int a,int b)

{

	int res=1;

	while(b)

	{

		if(b&1)res=(1LL*res*a)%MOD;

		a=(1LL*a*a)%MOD;

		b>>=1;

	}

	return res;

}

void prepare()

{

	fac[0]=1;

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

	fac[i]=(1LL*fac[i-1]*i)%MOD;

	inv[n+m]=fst_pow(fac[n+m],MOD-2);

	for(int i=n+m-1;i>=0;i--)

	inv[i]=(1LL*inv[i+1]*(i+1))%MOD;

}

int Comb(int a,int b)

{

	return 1LL*(1LL*fac[a]*inv[a-b]%MOD)*inv[b]%MOD;

}

int main()

{

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

	if(n<m)swap(n,m);

	prepare();

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

		ans=(ans+1LL*Comb(2*i,i)*Comb(n+m-2*i,n-i)%MOD)%MOD;

	ans=1LL*ans*fst_pow(Comb(m+n,n),MOD-2)%MOD;

	ans=1LL*ans*fst_pow(2,MOD-2)%MOD;

	printf("%d",ans+n);

}


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

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=1000005,md=998244353;

int n,m,ans;

int nyc[N],fac[N],facn[N];

inline int exgcd(int a,int b,int &x,int &y)

{

	if(b==0)

	{

		x=1;

		y=0;

		return a;

	}

	int t=exgcd(b,a%b,y,x);

	y-=a/b*x;

	return t;

}

inline int inv(int a)

{

	int x=0,y=0;

	exgcd(a,md,x,y);

	return (x+md)%md;

}

inline int C(int n,int m)

{

	return (ll)fac[n]*facn[m]%md*facn[n-m]%md;

}

inline int Cn(int n,int m)

{

	return (ll)facn[n]*fac[m]%md*fac[n-m]%md;

}

int main()

{

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

	inv(1);

	nyc[1]=1;

	fac[0]=facn[0]=fac[1]=facn[1]=1;

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

	{

		nyc[i]=(ll)(md-md/i)*nyc[md%i]%md;

		fac[i]=(ll)fac[i-1]*i%md;

		facn[i]=(ll)facn[i-1]*nyc[i]%md;

	}

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

		ans=(ans+(ll)C(n+m-2*i,n-i)*C(2*i,i)%md)%md;

	ans=(ll)ans*nyc[2]%md*Cn(n+m,n)%md;

	ans=(ans+max(n,m))%md;

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

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
/* Your prologue will be the story. */

/* Copyright by HenryLi */

#include<iostream>

#include<algorithm>

#include<queue>

#include<string>

#include<map>

#include<vector>

#include<set>

#include<sstream>

#include<stack>

#include<ctime>

#include<cmath>

#include<cctype>

#include<climits>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<iomanip>

#include<bitset>

#include<complex>

using namespace std;

template <class _T> inline void read(_T &_x) {

	int _t; bool _flag=false;

	while((_t=getchar())!='-'&&(_t<'0'||_t>'9')) ;

	if(_t=='-') _flag=true,_t=getchar(); _x=_t-'0';

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

	if(_flag) _x=-_x;

}

typedef long long LL;

const int maxn = 200010;

int n, a[maxn];

set<int> s;

int main() {

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

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

	read(n);

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

		read(a[i]);

		if (a[i] >= i || a[i] - a[i - 1] > 1) {

			puts("-1");

			return 0;

		}

	}

	LL ans = 0;

	for (int i = n; i >= 1; --i) {

		if (s.find(a[i] - i) != s.end()) continue;

		s.insert(a[i] - i);

		ans += a[i];

	}

	cout << ans << endl;

	return 0;

}


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

int a[200005],n;

long long ans;

int main()

{

	scanf("%d",&n);

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

	if(a[1]){puts("-1");return 0;}

	for(int i=2;i<=n;++i)if(a[i]<=a[i-1])ans+=a[i];

	else if(a[i]==a[i-1]+1)ans++;

	else {puts("-1");return 0;}

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

	return 0;

}

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

using namespace std;



int n,arr[200009];



int main()

{

    scanf("%d",&n);

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

    if(arr[1]>0)

    {

        printf("-1\n");

        return 0;

    }

    long long ans=0;

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

    {

        if(arr[i]-arr[i-1]>1)

        {

            printf("-1\n");

            return 0;

        }

        if(arr[i]-arr[i-1]==1)continue;

        ans+=arr[i-1];

    }

    ans+=arr[n];

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

    return 0;

}


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

int a[200005],n;

long long ans;

int main()

{

	scanf("%d",&n);

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

	if(a[1]){puts("-1");return 0;}

	for(int i=2;i<=n;++i)if(a[i]<=a[i-1])ans+=a[i];

	else if(a[i]==a[i-1]+1)ans++;

	else {puts("-1");return 0;}

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

	return 0;

}

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

using namespace std;

inline long long read(){

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

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

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

	return x*f;

}

#define MN 200005

long long n,a[MN];

long long ans;

int main(){

	n=read();bool ok=0;

	a[1]=read();if(a[1]>0) ok=1;

	register int i,j;

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

		a[i]=read();

		if(a[i]-a[i-1]>1) ok=1;

	}

	if(ok){

		puts("-1");

		return 0;

	}

	i=j=2;

	while(i<=n){

		for(;a[j+1]==a[j]+1;j++);

		ans+=a[j];i=j+1;j++;

	}

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

	return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<algorithm>

#define maxn 200005

#define inf 0x3f3f3f3f

using namespace std;

typedef long int ll;

int main()

{

    int n, t, x;

    long long ans = 0;

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

    if (t) return 0 & puts("-1");

    while(--n){

        scanf("%d", &x);

        if (x <= t) ans += x;

        else if (x == t + 1) ++ans;

        else return 0 & puts("-1");

        t = x;

    }

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

    return 0;

}


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

#include<cstring>

#include<cmath>

#include<iostream>

#include<cstdlib>

#include<map>

#include<stack>

#include<algorithm>

using namespace std;

const int N = 300000;



int main()

{

    int n,ch[N];

    long long int ans=0;

    scanf("%d",&n);

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

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

    if(ch[0]!=0) {printf("-1\n");return 0;}

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

    {

        if(ch[i]-ch[i-1]>=2) {printf("-1\n");return 0;}

        else if(ch[i]-ch[i-1]==1) ans++;

        else ans+=ch[i];

    }

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

    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<algorithm>

#define maxn 200005

#define inf 0x3f3f3f3f

using namespace std;

typedef long int ll;

int main()

{

    int n, t, x;

    long long ans = 0;

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

    if (t) return 0 & puts("-1");

    while(--n){

        scanf("%d", &x);

        if (x <= t) ans += x;

        else if (x == t + 1) ++ans;

        else return 0 & puts("-1");

        t = x;

    }

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

    return 0;

}


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

#include <cstdio>

using namespace std;

long long n, s, mx, a[200005];

int main() {

	long long i;

	scanf("%lld", &n);

	for(i=1; i<=n; i++) scanf("%lld", a+i);

	for(i=n; i; i--) {

		mx = max(mx-1, a[i]);

		if(a[i]<mx) mx=i=1;

		else if(a[i] == a[i-1]+1) s++;

		else s += a[i];

	}

	printf("%lld", mx>0 ? -1 : s);

	return 0;

}

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

long long n, s, a[200005];

int main() {

	scanf("%lld%lld", &n, a);

	if(a[0]>0) return !puts("-1");

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

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

		if(a[i] - a[i-1] > 1) return !puts("-1");

		else if(a[i] == a[i-1]+1) s++;

		else s += a[i];

	}

	printf("%lld", s);

	return 0;

}

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

using namespace std;



int main(void){

    long n;

    cin >> n;

    vector<long> a(n+1);

    a[0] = -1;

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

        cin >> a[i];

    }

    long count=-1;

    for(long i=n; i>=1; i--){

        long d = a[i]-a[i-1];

        if(d>=2){

            cout << -1 << endl;

            return 0;

        }else if(d<0){

            count += a[i];

        }else if(d==1){

            count++;

        }else{

            count += a[i];

        }

    }

    cout << count << endl;

    return 0;

}


// Optimized solution to the same problem (faster):
#include <stdio.h>



#define N 200000



long a[N+1];



int main(void){

    long n;

    scanf("%ld", &n);

    a[0] = -1;

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

        scanf("%ld", a+i);

    }

    long count=-1;

    for(long i=n; i>=1; i--){

        long d = a[i]-a[i-1];

        if(d>=2){

            puts("-1");

            return 0;

        }else if(d==1){

            count++;

        }else{

            count += a[i];

        }

    }

    printf("%ld\n", count);

    return 0;

}




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

#include<cstdio>

using namespace std;

int a[201000];long long ans=0;

int main()

{

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

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

	if(a[1]!=0)return 0*puts("-1");

	int now=0;

	for(int i=n;i>=2;i--)

	{

		if(a[i]<now)return 0*puts("-1");

		else if(a[i]==now){if(a[i]!=0)now--;}

		else now=a[i]-1,ans+=a[i];

	}

	if(now!=0)return 0*puts("-1");

	printf("%lld",ans);return 0;

}

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

#include<cctype>

#include<cstring>

#include<ctime>

#include<cstdlib>

#include<algorithm>

#define max(a,b) (a>b?a:b)

#define min(a,b) (a<b?a:b)

#define reg register

typedef long long ll;

template<typename T>inline T read(){

    reg T x=0;reg short f=1;reg char c=getchar();

    for(;!isdigit(c);f=c=='-'?-1:1,c=getchar());

    for(;isdigit(c);x=x*10+(c^48),c=getchar());

    return x*f;

}

int n,a[200005]={-1};

int main(){

	n=read<int>();reg ll ans=0;

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

		if((a[i]=read<int>())-a[i-1]>1)return 0*puts("-1");

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

		if(a[i]>a[i-1])ans++;

		else ans+=a[i];

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

	return 0;

}

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

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#define ll long long

using namespace std;

int n,now;

ll ans=0;

int a[200010];

int main(){

	scanf("%d",&n);

	int i,j;

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

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

	}

	if(a[1]!=0){

		printf("-1\n");return 0;

	}

	now=0;

	for(i=n;i>=1;--i){

		if(a[i]<now){

			printf("-1\n");return 0;

		}

		if(a[i]>now){

			now=a[i];ans=ans+(ll)a[i];

		}

		now--;now=max(now,0);

	}

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

	return 0;

}

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

#include<cctype>

#include<cstring>

#include<ctime>

#include<cstdlib>

#include<algorithm>

#define max(a,b) (a>b?a:b)

#define min(a,b) (a<b?a:b)

#define reg register

typedef long long ll;

template<typename T>inline T read(){

    reg T x=0;reg short f=1;reg char c=getchar();

    for(;!isdigit(c);f=c=='-'?-1:1,c=getchar());

    for(;isdigit(c);x=x*10+(c^48),c=getchar());

    return x*f;

}

int n,a[200005]={-1};

int main(){

	n=read<int>();reg ll ans=0;

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

		if((a[i]=read<int>())-a[i-1]>1)return 0*puts("-1");

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

		if(a[i]>a[i-1])ans++;

		else ans+=a[i];

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

	return 0;

}

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

#include<cstdio>

#include<cstring>

#include<cmath>

typedef long long ll;

using namespace std;

ll a[200000+50]={0};

int main ()

{

	ll n,i;

	cin>>n;

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

		cin>>a[i];

	if(a[0]!=0)

	{

		cout<<"-1"<<endl;

		return 0;

	}

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

	{

		if(a[i]-a[i-1]>1&&a[i]!=1)

		{

			cout<<"-1"<<endl;

			return 0;

		}

	}

	ll ans=0;

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

	{

		if(a[i-1]<a[i])

			ans+=1;

		else

			ans+=a[i];

	}

	cout<<ans<<endl;

	return 0;

 } 

// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <string.h>

#define R register

#define MN 200005

typedef long long ll;

namespace IO{

	inline int read(){

		R int x; R bool f; R char c;

		for (f=0; (c=getchar())<'0'||c>'9'; f=c=='-');

		for (x=c^'0'; (c=getchar())>='0'&&c<='9'; x=(x<<1)+(x<<3)+(c^'0'));

		return f?-x:x;

	}

}

namespace sol{

	int n,v[MN]={-1};ll ans;

	void main(){

		n=IO::read();

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

			if (v[i-1]+1<(v[i]=IO::read())) return (void)(puts("-1"));

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

			if (v[i]>=v[i+1]||i==n) ans+=v[i];

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

	}

}

int main(){sol::main();return 0;}

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

#include<cstdlib>

#include<iostream>

#include<queue>

#include<string>

#include<map>

#include<vector>

#include<algorithm>

#include<cstring>

using namespace std ;

const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};

int n;

long long a[200000+5];

int main()

{

    while(~scanf("%d",&n))

    {

        bool flag=1;

        long long sum=0;

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

        {

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

        }

        int x=-1;

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

        {

            x++;

            if(!flag) break;

            if(a[i]>x) {flag=0;break;}

            if(a[i])

            {

               if(a[i-1]>=a[i]) sum+=a[i];

               else if(a[i]-a[i-1]==1) sum++;

               else flag=0;

            }

            else

            {

                x=0;

            }

        }

        printf("%lld\n",flag?sum:-1);



    }



    return 0;

}


// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <string.h>

#define R register

#define MN 200005

typedef long long ll;

namespace IO{

	inline int read(){

		R int x; R bool f; R char c;

		for (f=0; (c=getchar())<'0'||c>'9'; f=c=='-');

		for (x=c^'0'; (c=getchar())>='0'&&c<='9'; x=(x<<1)+(x<<3)+(c^'0'));

		return f?-x:x;

	}

}

namespace sol{

	int n,v[MN]={-1};ll ans;

	void main(){

		n=IO::read();

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

			if (v[i-1]+1<(v[i]=IO::read())) return (void)(puts("-1"));

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

			if (v[i]>=v[i+1]||i==n) ans+=v[i];

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

	}

}

int main(){sol::main();return 0;}

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

using namespace std;

int n,a,l;

long long ans;

inline int read(){

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

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

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

    return x*f;

}

int main(){

	n=read(),a=read();

	if(a>0){

		puts("-1");

		return 0;

	}

	l=a;

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

		a=read();

		if(a==l+1) ans++;

		else if(a<l+1) ans+=a;

		else{

			puts("-1");

			return 0;

		}

		l=a;

	}

	printf("%lld",ans);

}

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

#include <algorithm>

#include <cstring>

#define INF 0x3f3f3f3f

#define LL long long

#define MAX 100010

using namespace std;

int a[200010];

long long sum=0;

int main()

{

    int N;

    scanf("%d",&N);

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

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

    if(a[0]!=0)

    {

        printf("-1\n");

        return 0;

    }

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

    {

        if(a[i]-a[i-1]>1)

        {

            printf("-1\n");

            return 0;

        }

        else if(a[i]-a[i-1]==1)

            sum++;

        else

            sum+=a[i];

    }

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

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):




#include<iostream>

using namespace std;

typedef long long ll;

ll a[200005];

int main(){

	ll n;while(cin>>n){

	a[0]=0;

	ll sum=0;

	bool flag=true;

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

		cin>>a[i];

		if(a[1]!=0||a[i]>a[i-1]+1){

			//cout<<"-1"<<endl;

			flag=false;//break;

		}

		else if(a[i-1]!=0&&a[i]==(a[i-1]+1)){

				sum+=1;//(a[i]-a[i-1]);

				}

		else sum+=a[i];}

		if(flag==true)

		cout<<sum<<endl;

	else cout<<"-1"<<endl;

	}

return 0;}


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



const int maxn=200000;



int read()

{

  int x=0,f=1;

  char ch=getchar();

  while((ch<'0')||(ch>'9'))

    {

      if(ch=='-')

        {

          f=-f;

        }

      ch=getchar();

    }

  while((ch>='0')&&(ch<='9'))

    {

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

      ch=getchar();

    }

  return x*f;

}



int n,a[maxn+10];

long long ans;



int main()

{

  n=read();

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

    {

      a[i]=read();

      if(a[i]>=i)

        {

          puts("-1");

          return 0;

        }

    }

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

    {

      if(a[i]>a[i-1]+1)

        {

          puts("-1");

          return 0;

        }

      if(a[i]==a[i-1]+1)

        {

          ++ans;

        }

      else

        {

          ans+=a[i];

        }

    }

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

  return 0;

}

// Fastest known solution for this problem: