#include <iostream>
#include <cstdio>
using namespace std;
int v[1002], l[1002][1002], ord[1002], mod[1002],quant[1002];
int main()
{
    freopen("subsiruri.in", "r", stdin);
    freopen("subsiruri.out", "w", stdout);
    int n, m, i, j, k, lmax = 1, in, fi, mid, pos;
    scanf("%d", &n);
    for(i = 1; i <=n; i++)
        scanf("%d", v+i);
        l[1][0] = 1;
        mod[1] = 1;
        mod[0] = 1;
        ord[0] = 1;
        ord[1] = 1;
        quant[1] = 1;
    for(i = 2; i <=n; i++)
    {
        in = 1;
        fi = lmax;
        while(in <= fi)
        {
            mid = (in+fi)/2;
            if(v[i] > v[l[mid][0]])
            {
                in = mid + 1;
            }
            else fi = mid - 1;
        }
        if(in > lmax) lmax = in;
        l[in][ord[in]++] = l[in][0];
        l[in][0] = i;
        if(in == 1){mod[1]++;quant[i] = 1;}
        else
    {
        pos = in;
        in = 1;
        fi = ord[pos - 1];
        k = mod[pos - 1];
        for(in; in < fi; in++)
        {
            if(v[i] > v[l[pos - 1][in]]) break;
            else k-=quant[l[pos - 1][in]];
        }
        quant[i] = k%9901;
        mod[pos] += k%9901;
        mod[pos] = mod[pos]%9901;
    }

    }
    printf("%d\n%d", lmax, mod[lmax]);
    return 0;
}