#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = ;

const ll mod = 1e9 + ;

ll dp[maxn][maxn], f[maxn][maxn], a[maxn];

int nex[maxn][maxn], pre[maxn][maxn];

pair<ll, int>discre[maxn];

int main(){

    int n;while(~scanf("%d", &n)){

        for(int i = ; i <= n; i ++){

            scanf("%lld", &a[i]);

            discre[i].first = a[i];

            discre[i].second = i;

        } sort(discre + , discre +  + n);

        discre[].first = -;

        int cnt = ;

        for(int i = ; i <= n; i ++){

            if(discre[i].first != discre[i - ].first) cnt ++;

            a[discre[i].second] = cnt;

        }

        a[] = a[n + ] = cnt + ;

        memset(dp, -, sizeof(dp));

        memset(nex, , sizeof(nex));

        memset(pre, , sizeof(pre));

        for(int i = ; i <= n + ; i ++){

            for(int j = i + ; j <= n + ; j ++)

                if(!nex[i][a[j]]) nex[i][a[j]] = j;

            for(int j = i - ; j >= ; j --)

                if(!pre[i][a[j]]) pre[i][a[j]] = j;

        }

        for(int l = n + ; l >= ; l -- ){

            ll ans1 = , ans2 = ;

            for(int r = l; r <= n + ; r ++){

                ll tmp1, tmp2;

                if(l == r){

                    dp[l][r] = f[l][r] = ;

                    continue;

                }

                if(a[r - ] <= a[l]){

                    tmp1 = dp[nex[l][a[r-]]][pre[r-][a[r-]]];

                    tmp2 =  f[nex[l][a[r-]]][pre[r-][a[r-]]];

                    if(ans1 == tmp1) ans2 = (ans2 - tmp2 + mod) % mod;

                    if(ans1 < tmp1) ans1 = tmp1, ans2 = tmp2;

                    tmp1 = dp[nex[l][a[r-]]][r - ];

                    tmp2 =  f[nex[l][a[r-]]][r - ];

                    if(ans1 == tmp1) ans2 = (ans2 + tmp2) % mod;

                    if(ans1 < tmp1) ans1 = tmp1, ans2 = tmp2;

                }

                if(a[l] == a[r]){

                    dp[l][r] = ans1 + ;

                    f[l][r] = ans2;

                }else dp[l][r] = f[l][r] = ;

            }

        }

        ll ans1 = , ans2 = ;

        for(int i = ; i <= cnt; i ++){

            if(dp[nex[][i]][pre[n+][i]] > ans1){

                ans1 = dp[nex[][i]][pre[n+][i]];

                ans2 =  f[nex[][i]][pre[n+][i]];

            }else if(ans1 == dp[nex[][i]][pre[n+][i]])

                ans2 = (ans2 + f[nex[][i]][pre[n+][i]]) % mod;

        }

        printf("%lld %lld\n",ans1, ans2);

    }

    return ;

}