#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(A) A.begin(),A.end()
#define vp cout<<'\n';
#define bp '\n'
const int MOD=1e9+7;
const int N=1e5+10;
int n,x;
vector<int>a;
deque<int>d;
int mx=0,cnt=0;
void rec(int i){
if(i==n){
vector<int>l;
for(auto&e:d){
//cout<<e<<' ';
auto p=lower_bound(all(l),e);
if(p==l.end()){
l.emplace_back(e);
}else{
*p=e;
}
}
//vp
if(l.size()==mx)++cnt;
else if(l.size()>mx){
mx=l.size();
cnt=1;
}
return ;
}
d.emplace_front(a[i]);
rec(i+1);
d.pop_front();
d.emplace_back(a[i]);
rec(i+1);
d.pop_back();
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n;
for(int i=0;i<n;++i){
cin>>x;
a.emplace_back(x);
}
d.emplace_back(a[0]);
rec(1);
cout<<mx<<' '<<cnt;
}
