# 2019杭电多校二 B Beauty Of Unimodal Sequence

#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define pb push_back
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;

const int N = 1e6+10;
int n, a[N],b[N],dp[N][2];
int c0[N],c1[N],ANS;
void add0(int x, int v) {
for (; x<=*b; x+=x&-x) c0[x]=max(c0[x],v);
}
int qry0(int x) {
int r = 0;
for (; x; x^=x&-x) r=max(r,c0[x]);
return r;
}
void add1(int x, int v) {
for (; x; x^=x&-x) c1[x]=max(c1[x],v);
}
int qry1(int x) {
int r = 0;
for (; x<=*b; x+=x&-x) r=max(r,c1[x]);
return r;
}
int ans[N];
void solve1() {
int mx = ANS, len = 0, pos = -1;
int f = 0;
REP(i,1,n) {
if (!len) {
if (dp[i][1]==mx) len=1,pos=i,ans[len]=i;
continue;
}
if (a[i]==a[pos]) continue;
if (a[i]>a[pos]) {
if (!f&&dp[i][1]==mx-len||f&&dp[i][0]==mx-len) {
++len,pos=i,ans[len]=i;
}
continue;
}
if (dp[i][0]==mx-len) {
f = 1, ++len,pos=i,ans[len]=i;
}
}
REP(i,1,len) {
if (i!=len) printf("%d ", ans[i]);
else printf("%d\n",ans[i]);
}
}
vector<pii> g0[N],g1[N];

int chk0(int L, int lst, int len) {
if (g0[len].empty()) return 0;
auto t = g0[len].back();
if (g0[len].back().x==L) {
g0[len].pop_back();
if (g0[len].empty()) {
g0[len].push_back(t);
return 0;
}
if (g0[len].back().y<lst) {
g0[len].push_back(t);
return 1;
}
else {
g0[len].push_back(t);
return 0;
}
}
if (g0[len].back().y<lst) return 1;
return 0;
}
int chk1(int L, int lst, int len) {
if (g1[len].empty()) return 0;
auto t = g1[len].back();
if (g1[len].back().x==L) {
g1[len].pop_back();
if (g1[len].empty()) {
g1[len].push_back(t);
return 0;
}
if (g1[len].back().y>lst) {
g1[len].push_back(t);
return 1;
}
else {
g1[len].push_back(t);
return 0;
}
}
if (g1[len].back().y>lst) return 1;
return 0;
}
void solve2() {
REP(i,1,n) g0[i].clear(),g1[i].clear();
PER(i,1,n) {
g0[dp[i][0]].pb(pii(i,a[i]));
g1[dp[i][1]].pb(pii(i,a[i]));
}
int mx = ANS, len = 0, pos = -1;
REP(i,1,mx) {
for (int j=1; j<g0[i].size(); ++j) {
g0[i][j].y = min(g0[i][j].y,g0[i][j-1].y);
}
for (int j=1; j<g1[i].size(); ++j) {
g1[i][j].y = max(g1[i][j].y,g1[i][j-1].y);
}
}
int f = 0;
REP(i,1,n) {
while (g1[mx-len].size()&&g1[mx-len].back().x<i) {
g1[mx-len].pop_back();
}
while (g0[mx-len].size()&&g0[mx-len].back().x<i) {
g0[mx-len].pop_back();
}
if (!len) {
if (g1[mx].size()==1&&g1[mx].back().x==i) len=1,pos=i,ans[len]=i;
continue;
}
if (a[i]==a[pos]) continue;
if (f) {
if (chk0(i,a[pos],mx-len)) continue;
}
else {
if (chk1(i,a[pos],mx-len)) continue;
if (chk0(i,a[pos],mx-len)) continue;
}
if (a[i]<a[pos]) f=1;
++len,pos=i,ans[len]=i;
if (len==mx) break;
}
REP(i,1,len) {
if (i!=len) printf("%d ", ans[i]);
else printf("%d\n",ans[i]);
}
}

int main() {
while (~scanf("%d", &n)) {
REP(i,1,n) scanf("%d", a+i);
REP(i,1,n) b[i]=a[i];
sort(b+1,b+1+n);
*b=unique(b+1,b+1+n)-b-1;
REP(i,0,*b+5) c0[i]=c1[i]=0;
REP(i,0,n+5) dp[i][0]=dp[i][1]=0;
REP(i,1,n) a[i]=lower_bound(b+1,b+1+*b,a[i])-b;
//dp[0] 为全递减
//dp[1] 为递增再递减
ANS = 0;
PER(i,1,n) {
if (a[i]!=1) dp[i][0] = qry0(a[i]-1);
++dp[i][0];
dp[i][1] = max(dp[i][0], qry1(a[i]+1)+1);