stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.2306549196746035x):
#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;

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

}


// Faster C++ solution for the same problem (measured speedup: 5.4123239198121595x):
#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;

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

}

// Faster C++ solution for the same problem (measured speedup: 5.26576825553222x):
#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;

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

}


// Faster C++ solution for the same problem (measured speedup: 5.3207323770636785x):
#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;

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

}

// Faster C++ solution for the same problem (measured speedup: 5.306931459320331x):
#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;

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

}

// Faster C++ solution for the same problem (measured speedup: 5.3084123576278754x):
#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;

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

 } 

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

using namespace std;

int v[200005];

int main() {

    int n;

    scanf("%d",&n);

    bool f=true;

    long long s=0;

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

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

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

    {

        if(v[i]>i||(i<n-1&&v[i]+1<v[i+1]))

            f=false;

        else if(i<n-1&&v[i]+1==v[i+1])continue;

        else s+=v[i];

    }

    if(f)

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

    else

        printf("-1\n");

    return 0;

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

}


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

using namespace std;

int v[200005];

int main() {

    int n;

    scanf("%d",&n);

    bool f=true;

    long long s=0;

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

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

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

    {

        if(v[i]>i||(i<n-1&&v[i]+1<v[i+1]))

            f=false;

        else if(i<n-1&&v[i]+1==v[i+1])continue;

        else s+=v[i];

    }

    if(f)

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

    else

        printf("-1\n");

    return 0;

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

 } 

// Faster C++ solution for the same problem (measured speedup: 5.387451009700524x):
#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;}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.3289517428860185x):
#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;}
// Slower C++ solution:
#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;

 } 

// Faster C++ solution for the same problem (measured speedup: 5.288534828751906x):
#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;

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

}


// Faster C++ solution for the same problem (measured speedup: 5.231109636495324x):
#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;

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

}

// Faster C++ solution for the same problem (measured speedup: 5.195142346491363x):
#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;

}
// Slower C++ solution:




#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;}


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

#include<cstring>

#include<algorithm>

#define MN 200005

#define ll long long

using namespace std;

inline int in(){

    int x=0;bool f=0; char c;

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

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

    return f?-x:x;

}

ll res;

int a[MN],n;

int main()

{

	n=in();

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

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

		if (a[i]-a[i-1]>=2||a[i]>=i) {printf("-1");return 0;}

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

		else res+=1ll*a[i];

	}printf("%lld",res);return 0;

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

using namespace std;



#define mp make_pair

#define pb push_back



typedef pair<int, int> ii;

typedef long long ll;

typedef pair<ll, ll> l4;



const int maxn = 2e5+1;

int a[maxn], n;

inline void end()

{

  puts("-1");

  exit(0);

}

int main()

{

  scanf("%d", &n);

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

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

  if (a[1] != 0)

    end();

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

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

      end();

  deque<int> dq;

  ll base = 0;

  ll ans = 0;

  for (int i = n; i >= 1; --i, --base)

    {

      while (!dq.empty() && dq.front()+base <= 0)

        dq.pop_front();

      if (a[i] == 0)

        continue;

      if (dq.empty() || dq.back()+base != a[i])

        dq.push_back(a[i]-base);

      ans += dq.size();

    }

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

}


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

#include<cstring>

#include<algorithm>

#define MN 200005

#define ll long long

using namespace std;

inline int in(){

    int x=0;bool f=0; char c;

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

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

    return f?-x:x;

}

ll res;

int a[MN],n;

int main()

{

	n=in();

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

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

		if (a[i]-a[i-1]>=2||a[i]>=i) {printf("-1");return 0;}

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

		else res+=1ll*a[i];

	}printf("%lld",res);return 0;

}
// Slower C++ solution:




#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;}


// Faster C++ solution for the same problem (measured speedup: 5.3875003718601615x):
#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;

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

using namespace std;



#define mp make_pair

#define pb push_back



typedef pair<int, int> ii;

typedef long long ll;

typedef pair<ll, ll> l4;



const int maxn = 2e5+1;

int a[maxn], n;

inline void end()

{

  puts("-1");

  exit(0);

}

int main()

{

  scanf("%d", &n);

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

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

  if (a[1] != 0)

    end();

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

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

      end();

  deque<int> dq;

  ll base = 0;

  ll ans = 0;

  for (int i = n; i >= 1; --i, --base)

    {

      while (!dq.empty() && dq.front()+base <= 0)

        dq.pop_front();

      if (a[i] == 0)

        continue;

      if (dq.empty() || dq.back()+base != a[i])

        dq.push_back(a[i]-base);

      ans += dq.size();

    }

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

}


// Faster C++ solution for the same problem (measured speedup: 5.355222185305486x):
#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;

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

#define fi first

#define se second

#define LL long long



using namespace std;

const int maxn = 2e5 + 5;

typedef pair<int, int> P;



int a[maxn];



int main() {

#ifdef TT

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

#endif // TT

    int n, i, x;

    LL ans = 0;

    scanf("%d", &n);

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

    for(i = n - 1, x = 0;i >= 0; i--) {

        if(a[i] > i || a[i] < x) return puts("-1"), 0;

        if(a[i] > x) {

            ans += a[i];

            x = a[i];

        }

        x = max(x - 1, 0);

    }

    cout << ans << endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.313249276490176x):
#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;

}