#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using vll = vector<ll> ;
#define all(v) v.begin(),v.end()
const ll mod = 1e9+7;

int main(){
  ll N;cin>>N;
  vector<int> A(N);rep(i,N)cin>>A[i];
  map<int,int> m;
  ll ans = 1;
  rep(i,N){
    m[A[i]]++;
    if(A[i]==0){
      ans *= 4 - m[0];
    }
    else{
      ans *= (m[A[i]-1] - m[A[i]] + 1);
    }
    ans %= mod;
  }
  cout << ans << endl;
}
#include <bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;

const ll MAXN = 200000;
const ll INF = 1001001001;

ll N, ans=0, tmp=0;
vector<ll> A;

signed main(){
    cin >> N;
    for(int i=0;i<N;i++) {
        ll a;
        cin >> a;
        if(i==0&&a!=0) {
            cout << -1 << endl;
            return 0;
        }
        if(tmp+1<a) {
            cout << -1 << endl;
            return 0;
        }
        else {
            if(tmp+1>a) {
                ans += a;
            }
            else {
                ans += a-tmp;
            }
        }
        tmp = a;
    }
    cout << ans << endl;
    return 0;
}