/*导弹拦截系统的套数 即 最少链划分数 ,最少链划分数 就是 最大反链长度 */
# include <stdio.h>
# include <stdlib.h>
void LIS(int a[] , int b[] , int n)
{
int max1 = 0 ;
int max2 = 0 ;
int i , j ;
for ( i = 0; i < n; i++ )
b[i] = 1;
for (i = n-2 ; i >= 0 ; i--)
for (j = n-1 ; j > i ; j--)
if (a[i] > a[j] && b[i] < b[j] + 1)
b[i] = b[j] + 1 ;
for (i = 0 ; i < n ; i++)
{
if (b[i] > max1)
max1 = b[i] ;
}
for ( i = 0; i < n; i++ )
b[i] = 1;
for (i = 1 ; i < n ; i++)
for (j = 0 ; j < i ; j++)
if (a[i] > a[j] && b[i] < b[j] + 1)
b[i] = b[j] + 1 ;
for (i = 0 ; i < n ; i++)
{
if (b[i] > max2)
max2 = b[i] ;
}
printf("%d %d\n" , max1 , max2);
}
int main ()
{
int n ;
int i ;
scanf("%d" , &n);
int a[1001] ;
for (i = 0 ; i < n ; i++)
scanf("%d" , &a[i]);
int b[1001] ;
LIS(a , b , n) ;
return 0 ;
}