#include <iostream>
using namespace std;

void bubble(int *pbuff, int n){
	int v;
	int j;
	int flag=1;
	int i=0;
	int count=0;
	while(flag){
		flag=0;
		for(int i=n-1;j<i;i--){
			if(pbuff[i]<pbuff[i-1]){
				v=pbuff[i];
				pbuff[i]=pbuff[i-1];
				pbuff[i-1]=v;
				count++;
			}
			flag=1;
		}
		j++;
	}
		for(int j=0;j<n-1;j++) cout << pbuff[j]<<" ";
		cout << pbuff[n-1]<<endl;
		cout << count<<endl;
	return ;
}

int main()
{
	int n;
	cin>> n;
	int buff[100];
	for(int j=0;j<n;j++) cin >> buff[j];
	bubble(buff,n);
	return 0;
}


//FIRST THINK THEN CODE.

#include <bits/stdc++.h>
 
 
using namespace std;
 
typedef long long ll;
 
//#define MOD 998244353
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define rrep(i,a,b) for(ll i=a;i>b;--i)
#define FOR(i,n)  for(ll i=0;i<n;i++)
#define vi vector<int>
#define vl vector<ll>
#define ld long double
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define pii pair<int,int>
#define pll pair<long,long>
#define vpii vector<pii>
#define vpll vector<pll>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define d1(x) cout<<(x)<<endl
#define d2(x,y) cout<<(x)<<" "<<(y)<<endl
#define d3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
#define d4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl
#define PI 3.1415926535897932384626433832795
#define fix(f,n) fixed<<setprecision(n)<<f
#define all(x) x.begin(),x.end()
#define rev(p) reverse(p.begin(),p.end());
#define endl "\n"
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define popcount(x) __builtin_popcountll(x)
#define sz(x) ((ll)x.size())
const ll M=1000000007;
const ll MM=998244353;
int begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";

 
ll newmod(ll a,ll b)
 {
  return ((a%b)+b)%b;
}
 
 
ll powM(ll a,ll b,ll m )
{ 
  if(a<=0)return 0;
  a%=m;
  if(!b)return 1;
  ll ans=1LL;
  while(b)
  {
    if(b&1)ans=ans*a%m;
    a=a*a%m;
    b>>=1;
  }
 
return ans;
}


 
ll poww(ll a,ll b)
{ 
  
  ll ans=1;
  while(b)
  {
    if(b&1)ans=ans*a;
    a=a*a;
    b>>=1;
  }
 
return ans;

}

template<typename T,typename F>
void chmax( T &a,F b){
  if(b>a)a=b;
}

template<typename T,typename F>
void chmin( T &a,F b){
  if(b<a)a=b;
}

const ll N=1e5+5;



int main()
{ 

IOS;


ll n;cin>>n;

vl f(N);

ll ans=1;

for(int i=1;i<=n;i++){
  ll x;cin>>x;
  ll temp;
  if(!x){
    temp=3-f[0];
  }
  else {
    temp=f[x-1]-f[x];
  }
  if(temp<=0){
    cout<<0;
    return 0;
  }
  ans=ans*temp%M;
  f[x]++;
}

cout<<ans;

//end_routine();

return 0;
 
}
