#include <bits/stdc++.h>
using namespace std;

const int BIG=1000*1000*1000+1;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	vector<int> samples(n);
	for(int &x:samples){
		cin>>x;
	}
	vector<int> smallestLeft(n);
	vector<int> biggestLeft(n);
	vector<int> smallestHigherLeft(n);
	vector<int> biggestLowerLeft(n);
	vector<bool> hasSameLeft(n);

	vector<int> biggestRight(n);
	vector<int> smallestRight(n);
	vector<int> smallestHigherRight(n);
	vector<int> biggestLowerRight(n);
	vector<bool> hasSameRight(n);
	vector<bool> hasMiddleSmaller(n);
	vector<bool> hasMiddleLarger(n);
	{
		set<int> have;
		have.insert(samples[0]);
		for(int i=1;i<n-1;i++){
			smallestLeft[i]=*have.begin();
			biggestLeft[i]=*(--have.end());
			auto candidateSH=have.lower_bound(samples[i]+1);
			if (candidateSH==have.end())
			{
				smallestHigherLeft[i]=BIG;
			}
			else
			{
				smallestHigherLeft[i]=*candidateSH;
			}
			auto candidateBL=have.upper_bound(samples[i]-1);
			if (candidateBL==have.begin())
			{
				biggestLowerLeft[i]=-1;
			}
			else
			{
				auto result=*(--candidateBL);
				biggestLowerLeft[i]=result;
			}
			hasSameLeft[i]=(have.find(samples[i])!=have.end());
			have.insert(samples[i]);
		}
	}
	{
		set<int> have;
		have.insert(samples[n-1]);
		for(int i=n-2;i>0;i--){
			smallestRight[i]=*have.begin();
			biggestRight[i]=*(--have.end());
			auto candidateSH=have.lower_bound(samples[i]+1);
			if (candidateSH==have.end())
			{
				smallestHigherRight[i]=BIG;
			}
			else
			{
				smallestHigherRight[i]=*candidateSH;
			}
			auto candidateBL=have.upper_bound(samples[i]-1);
			if (candidateBL==have.begin())
			{
				biggestLowerRight[i]=-1;
			}
			else
			{
				biggestLowerRight[i]=*(--candidateBL);
			}
			hasSameRight[i]=(have.find(samples[i])!=have.end());
			have.insert(samples[i]);
		}
	}
	{
		vector<int> closestSameLeft(n);
		map<int, int> M;
		for (int i = 0; i < n; ++i) {
			const int x = samples[i];
			if (M.count(x)) {
				closestSameLeft[i] = M[x];
			} else {
				closestSameLeft[i] = -1;
			}
			M[x] = i;
		}
		//for (int x : closestSameLeft) cerr << x << ' ';
		//cerr << endl;
		int p2 = 1;
		while (p2 < n) p2*=2;
		vector<int> tmax(2*p2, INT_MIN), tmin(2*p2, INT_MAX);
		copy_n(samples.begin(), n, tmax.begin() + p2);
		copy_n(samples.begin(), n, tmin.begin() + p2);
		for (int i = p2 - 1; i > 0; --i) {
			tmax[i] = max(tmax[2*i], tmax[2*i+1]);
			tmin[i] = min(tmin[2*i], tmin[2*i+1]);
		}
		auto querymin = [p2,&tmin](int i, int j) {
			i += p2; j += p2;
			int ret = INT_MAX;
			while (i < j) {
				if (i&1) ret = min(ret, tmin[i++]);
				if (j&1) ret = min(ret, tmin[--j]);
				i /= 2;
				j /= 2;
			}
			return ret;
		};
		auto querymax = [p2,&tmax](int i, int j) {
			i += p2; j += p2;
			int ret = INT_MIN;
			while (i < j) {
				if (i&1) ret = max(ret, tmax[i++]);
				if (j&1) ret = max(ret, tmax[--j]);
				i /= 2;
				j /= 2;
			}
			return ret;
		};
		for (int i = 2; i < n; ++i) {
			const int l = closestSameLeft[i];
			if (l == -1 || l == i - 1) continue;
			//cerr << "candidate " << i << ' ' << l << endl;
			//cerr << querymin(l+1,i) << ' ' << querymax(l+1,i) << endl;
			if (querymax(l+1,i) > samples[i]) hasMiddleLarger[i] = true;
			if (querymin(l+1,i) < samples[i]) hasMiddleSmaller[i] = true;
		}
	}
	
	set<int> results;
	for(int i=1;i<n;i++){
		auto current=samples[i];
		if (hasSameLeft[i]&&hasSameRight[i]){
			results.insert(111);
		}
		if (hasSameLeft[i]&&biggestRight[i]>current){
			results.insert(112);
		}
		if (hasSameLeft[i]&&smallestRight[i]<current){
			results.insert(221);
		}
		if (hasSameRight[i]&&biggestLeft[i]>current){
			results.insert(211);
		}
		if (hasSameRight[i]&&smallestLeft[i]<current){
			results.insert(122);
		}
		if(biggestLowerLeft[i]>smallestRight[i]){
			results.insert(231);
		}
		if(smallestLeft[i]<current && current<biggestRight[i]){
			results.insert(123);
		}
		if(smallestLeft[i]<biggestLowerRight[i]){
			results.insert(132);
		}
		if(biggestLeft[i]>current && current>smallestRight[i]){
			results.insert(321);
		}
		if(biggestLeft[i]>smallestHigherRight[i]){
			results.insert(312);
		}
		if(smallestHigherLeft[i]<biggestRight[i]){
			results.insert(213);
		}
		if(hasMiddleSmaller[i])
			results.insert(212);
		if(hasMiddleLarger[i])
			results.insert(121);
	}
	for (auto result : results){
		cout<<result<<endl;
	}
}