1 #include 
     
       2 #define _for(i,a,b) for(int i = (a);i < b;i ++) 3 typedef long long ll; 4 using namespace std; 5 inline bool read(int &x) 6 { 7     char c=getchar(); 8     if(c==EOF)return false; 9     while(c>'9'||c<'0')c=getchar();10     while(c>='0'&&c<='9')11     {12         x=(x<<1)+(x<<3)+(c^48);13         c=getchar();14     }15     return true;16 }17 18 int a[100003];19 int dp1[100003];20 int dp1sum = 1;21 int dp2[100003];22 int dp2sum = 1;23 int n = 0;24 int main()25 {26     memset(a,0,sizeof(a));27     while(read(a[n++]));n--;28     29     dp2[1] = dp1[1] = a[0];30     _for(i,1,n)31     {32         if(a[i]<=dp1[dp1sum])33             dp1[++dp1sum] = a[i];    34         else35         {36             int k = upper_bound(dp1+1,dp1+dp1sum+1,a[i],greater
      
       ())-dp1;37             dp1[k] = a[i];38         }39         if(a[i]>dp2[dp2sum])40             dp2[++dp2sum] = a[i];41         else42         {43             int k = lower_bound(dp2+1,dp2+dp2sum+1,a[i])-dp2;44             dp2[k] = a[i];45         }46     }47     printf("%d\n",dp1sum);48     printf("%d\n",dp2sum);49     return 0;50 }