1 #include<map>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 const int M=100009;
 6 map <pair<int,int>,int> mp;
 7 int i,n,top,a[M],st[M],f1[M],f2[M];
 8 bool flag[M];
 9 
10 void LIS(int *f)
11 {
12     st[top=1]=a[1]; f[1]=1;
13     for (int i=2;i<=n;++i)
14         if (st[top]<a[i]) st[++top]=a[i],f[i]=top;
15         else
16         {
17             int l=1,r=top,ans=0;
18             while (l<=r)
19             {
20                 int mid=l+r>>1;
21                 if (st[mid]<a[i]) ans=mid,l=mid+1; else r=mid-1;
22             }
23             st[ans+1]=a[i];
24             f[i]=ans+1;
25         }
26 }
27 
28 int main()
29 {
30     scanf("%d",&n);
31     for (i=1;i<=n;++i) scanf("%d",&a[i]);
32     LIS(f1);
33     for (i=1;i<=n;++i) a[i]=M-a[i];
34     for (i=1;i+i<=n;++i) swap(a[i],a[n+1-i]);
35     LIS(f2);
36     for (i=1;i+i<=n;++i) swap(f2[i],f2[n+1-i]);
37     ++top;
38     for (i=1;i<=n;++i)
39         if (f1[i]+f2[i]==top) ++mp[make_pair(f1[i],f2[i])];
40         else flag[i]=1;
41     for (i=1;i<=n;++i)
42         if (!flag[i])
43             if (mp[make_pair(f1[i],f2[i])]==1) printf("3");
44             else printf("2");
45         else printf("1");
46     return 0;
47 }