#include<bits/stdc++.h>
using namespace std;
#define int long long

int N,v[1000001],f[1000001];
int nl=-1,cnt=1;
bool flag=false;

int Binary_s(int a,int l,int r)
{
  if(l==r)
    return l;
  int mid=(l+r)>>1;
  if(a==f[mid])
    return mid;
  if(a>f[mid])
    return Binary_s(a,mid+1,r);
  if(a<=f[mid])
    return Binary_s(a,l,mid);
}

signed main()
{
//  freopen("buy.in","r",stdin);
//  freopen("buy.out","w",stdout);
  scanf("%lld",&N);
  scanf("%lld",&v[0]);
  f[++nl]=v[0];
  for(int i=1; i<N; i++)
  {
    scanf("%d",&v[i]);
    int pos=nl;
    if(v[i]<f[nl])
    {
      flag=true;
      f[++nl]=v[i];
    }
    else
    {
      flag=false;
      pos=Binary_s(v[i],0,nl);
      f[pos+1]=v[i];
    }
    if(flag==true)
      cnt=0;
    else
    {
      cnt++;
    }
  }
  cout<<nl+1<<' '<<cnt<<endl;
  return 0;
}