// Longest strictly increasing subsequence
// Based on D. Gries, The Science of Programming, p. 262
// which is based on M. Fredman, Discrete Mathematics 11 (1975),
//   29-35.

#include <stdio.h>

#define MAXN (1000)

main()
{
int n;
int b[MAXN];        // Input sequence
int m[MAXN+1];      // m[i] is the smallest value for an SIS with i numbers
int seq[MAXN+1];    // Result sequence
int sub[MAXN+1];    // Predecessor to b[i] in  some SIS
int mLink[MAXN+1];  // The value j for the b[j] last used to set m[i]
int i,j,k,mid,low,high;

scanf("%d",&n);
for (i=0;i<n;i++)
  scanf("%d",&b[i]);

k=1;
m[1]=b[0];
sub[0]=(-1);
mLink[1]=0;
for (i=1;i<n;i++)
  if (b[i]==m[k])
  {
    printf("b[%d]==%d skipped\n",i,b[i]);
    continue;
  }
  else if (b[i]>m[k])
  {
    k++;
    m[k]=b[i];
    sub[i]=mLink[k-1];
    mLink[k]=i;
  }
  else if (b[i]<m[1])
  {
    m[1]=b[i];
    sub[i]=(-1);
    mLink[1]=i;
  }
  else
  {
    low=1;
    high=k;
    printf("start search\n");
    while (low!=high-1)
    {
      printf("low %d high %d\n",low,high);
      mid=(low+high)/2;
      if (m[mid]<=b[i])
        low=mid;
      else
        high=mid;
    }
    // Check search result
    if (m[low]>b[i] || m[high]<=b[i])
      printf("error\n");
    if (m[high-1]==b[i])
    {
      printf("b[%d]==%d skipped\n",i,b[i]);
      continue;
    }
    m[high]=b[i];
    sub[i]=mLink[high-1];
    mLink[high]=i;
  }
printf("  i     b     m    mLink sub\n");
for (i=0;i<n;i++)
{
  printf("%5d %5d ",i,b[i]);
  if (i==0 || i>k)
    printf("            ");
  else
    printf("%5d %5d ",m[i],mLink[i]);
  printf("%3d\n",sub[i]);
}
printf("k is %d\n",k);
// Get result sequence
i=mLink[k];
for (j=k-1;j>=0;j--)
{
  seq[j]=b[i];
  i=sub[i];
}
for (i=0;i<k;i++)
  printf("%4d %4d\n",i,seq[i]);
}