#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph= vector<vector<int>>; 
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
// ミント
const int mod = 1e9+7 ;
//998244353;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
//昆布
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
}   ;
 
 
int main(){
 ll n ;cin>> n;
 vector<ll> A(n) ;
 ll dai = -INF ;
 rep(i,n){
   cin>>A[i] ;
   chmax(dai,A[i]) ;
 }
 vector<vector<ll>> P(dai+1,vector<ll>(3,INF)) ;
 
 vector<ll> Q(dai+1) ; //カウント
 ll ans=1 ;
 rep(i,n){
   if(Q[A[i]]==3){
     ans= -1 ;
     break ;
   }
   P[A[i]][Q[A[i]]]=i;
   Q[A[i]]++ ;
   
 }
 if(ans==-1) cout<<0<<endl ;
 else{
   rep(i,dai+1){
     if(i==0){
       if(P[i][0]==INF) ans=0 ;
       else if(P[i][1]==INF) ans=3 ;
       else if(P[i][2]==INF) ans=6 ;
       else ans=6 ;
     }
    
    else{
      ll seki=0 ;
      ll a=P[i-1][0] ; ll b=P[i-1][1] ; ll c=P[i-1][2] ;
      ll d=P[i][0] ; ll e=P[i][1] ; ll f=P[i][2] ;
    ll mae=0 ;ll ato=0 ;
    if(a==INF) {mae++ ;a-- ;}
      if(b==INF) {mae++ ;b--  ;}
      if(c==INF) {mae++ ;c--;}
    if(d==INF) {ato++ ;}
    if(e==INF) {ato++  ;}
    if(f==INF) {ato++  ;}
    if(mae==3||ato==3||mae>ato) ans=0 ;
    //６通り列挙
    if(a<d&&b<e&&c<f) seki++ ;
    if(a<d&&b<f&&c<e) seki++ ;   
    if(a<e&&b<d&&c<f) seki++ ;
    if(a<e&&b<f&&c<d) seki++ ;
    if(a<f&&b<d&&c<e) seki++ ;
    if(a<f&&b<e&&c<d) seki++ ;
    if(mae==2&&ato==2) seki= seki/2 ;
    if(mae==1&&ato==2) seki= seki/2 ;
    if(mae==0&&ato==2) seki= seki/2 ;
    ans= (ans*seki)%(1000000007ll) ;
    }
   
   if(ans==0) break ;
   }
   cout<<ans<<endl ;
 }
  
    return 0;
  }

Measured memory_bytes: 7296