/*导弹拦截系统的套数 即 最少链划分数 ，最少链划分数 就是 最大反链长度 */

# 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 ;

}