/*
PROB: buylow
LANG: C++
*/
/*
這道題很有意思，乍一看，它就是最長下降子序列，第一個問題確實是這樣，對于5000的規模我們很容易給出O(NlogN)的算法。
不過這道題目的第二問是要得出最長序列的個數，而且序列相同位置不同的都只能算一個。不知道各位大牛有沒有NLgN的算法，反正我是想不出了……
那么都用N^2的動歸算法吧，第一個問題：
ls[i]=max{ ls[j] | 0 <= j < i ,p[j]>p[i] }+1;
其中，ls[i]為第i個數字為結尾的序列中最長下降子序列的長度，p[i]為輸入的第i天的股價。

考慮第二問，如果不牽扯重復的問題，那么遞推式容易給出，如下：
countt[i]=sum{ countt[j] | 0 <= j < i ,p[j]>p[i] , ls[i]==ls[j]+1};
這其實是加法原則的應用，要得到第i個長度為m的序列有多少種，只需計算0 ~ i-1中所有價格高于i的，并別長度為m-1的序列個數之和！

  在處理去重復問題時，我借鑒了某大牛的一種方法：
  建立數組next[MAXV]，對于序列中任意元素i，next[i]的值為i ~ n-1中的第一個價格等于p[i]的位置。如果沒有，就為0
  這樣，我們在處理countt相加時，對于每一個j，只需保證next[j]==0 || next[j]>i就可以，意思就是在當前j ~ i-1的區間中沒有價格等于j的元素了，這樣，總是處理區間中重復元素的最后一個！
  
最后要特別注意，countt的值會非常大，所以相加時必須用高精度加法！
*/
#include<iostream>
#include<fstream>
#include<algorithm>
#define MAXV 5002
#define cin fin
using namespace std;
ifstream fin("buylow.in");
ofstream fout("buylow.out");
int p[MAXV];
int ls[MAXV];
int next[MAXV];
char countt[MAXV][1001];
int top,m,n;
char sum[1001];
inline int maxf(int a,int b)
{
    return a>b?a:b;
}
void pluschar(char *a,char *b)
{
    int length,pl,i;
    length=maxf(a[1000],b[1000]);
	a[1000]=length;
    i=0;pl=0;
    while(length>0)
    {
        pl=(a[i]-'0')+(b[i]-'0')+pl;
        a[i]=pl%10+'0';
        pl/=10;
        i++;
        length--;
    }
    if(pl>0) {a[i]='1'; a[1000]++;}
}
void writes(char *s)
{
	int i;
	for(i=s[1000]-1;i>=0;i--) fout<<s[i];
	fout<<endl;
}
int main()
{
    int i,j,k,maxt;
    memset(countt,'0',sizeof(countt));
    memset(sum,'0',sizeof(sum));
    cin>>n;
    for(i=0;i<=n;i++) countt[i][1000]=0;
    sum[1000]=0;
    for(i=0;i<n;i++) cin>>p[i];
    for(i=0;i<n;i++)
        for(next[i]=0,j=i+1;j<n;j++)
        if(p[i]==p[j]) {next[i]=j; break;}
    ls[0]=1;
    for(i=1;i<n;i++)
    {
        for(j=0,maxt=0;j<i;j++)
        {
            if(p[j]>p[i] && ls[j]>maxt) maxt=ls[j];
        }
        ls[i]=maxt+1;
    }
    for(i=0,maxt=0;i<n;i++) if(ls[i]>maxt) maxt=ls[i];
    fout<<maxt<<' ';
	ls[n]=maxt+1;
    for(i=0;i<=n;i++)
    {
		//if(next[i]!=0 && ls[i]==ls[next[i]]) continue;
        if(ls[i]==1)
        {
            countt[i][0]='1';
            countt[i][1000]=1;
            continue;
        }
        for(j=0;j<i;j++)
        {
            if(p[j]>p[i] && ls[i]==ls[j]+1 && (next[j]==0 || next[j]>i))
                pluschar(countt[i],countt[j]);
        }

    }
    writes(countt[n]);
    return 0;
}