#include <iostream>
#include <vector>
#include <map>
using namespace std;

int dp[5001];
int value[5001];
int ans;
map<pair<int,int>,int> m;
vector<int> vec[66000];

int Max(int a,int b){
	return (a>b)? a:b; 	
}

void GetAns(int n){
	int cnt=0;
	int D[5001];
	for (int i=0;i<n;i++){
		if (cnt &&  D[cnt]>value[i])
			D[++cnt]=value[i],dp[i]=cnt;
		else if (!cnt)
			D[++cnt]=value[i],dp[i]=1;
		else
			{
				int left=1,right=cnt,mid;
				while (left<=right){
					mid=(left+right)/2;
					if (D[mid]<=value[i])
						right=mid-1;
					else
						left=mid+1;
				}
				D[left]=Max(D[left],value[i]);
				dp[i]=left;
			}
		}
	ans=cnt;
}

int main()
{
	int n,i,j;cin>>n;
	for (i=0;i<n;i++) scanf("%d",value+i);
	GetAns(n);
	for (i=0;i<n;i++){
		vec[value[i]].clear();
		for (j=0;j<i;j++){
			if (value[j]>value[i] && dp[j]==dp[i]-1){
				if (  vec[value[i]].empty() || value[j]>vec[value[i]].back())
					vec[value[i]].push_back(value[j]);
			}
		}
		int size=vec[value[i]].size();
		int temp=0;
		for (j=0;j<size;j++) temp+=m[make_pair(vec[value[i]][j],dp[i]-1)];
		if (dp[i]==1) {
			if (m.find(make_pair(value[i],1))==m.end()) m.insert(make_pair(make_pair(value[i],1),1));
		}else {
			pair<int,int> p=make_pair(value[i],dp[i]);
			if (m.find(p)==m.end()) m.insert(make_pair(p,temp));
			else m[p]=temp;
		}
	}
	int Cnt=0;
	map<pair<int,int>,int> ::iterator e,End=m.end();
	for (e=m.begin();e!=End;e++)
		if (e->first.second==ans)
			Cnt+=e->second;
	cout<<ans<<' '<<Cnt<<endl;
	return 0;
}