Mika i Laza igraju igru kartama. Špil sadrži n karata, pri čemu i-ta karta vredi a_i poena. Oni izvlače karte u redosledu u kome se nalaze u špilu, počevši od dna. I Mika i Laza na početku imaju po 0 poena i svaki put kada neki igrač izvuče kartu, broj njegovih poena se povećava za vrednost te karte. Prvo izvlači Mika, a zatim izvlači onaj igrač koji u tom trenutku ima manje poena. Ako imaju jednak broj poena, izvlači Mika.

Međutim, ono što Laza ne zna a Mika zna je početni raspored karata. Naravno, Mika hoće da vara tako što će preseći špil na nekom mestu i zatim početi igru. Pod sečenjem se podrazumeva standardno sečenje: izabere se proizvoljna pozicija u špilu i sve karte iznad te pozicije se prebace na dno špila, ne menjajući međusobni poredak. Odrediti koliko najviše poena može osvojiti Mika varanjem i na koliko načina može to postići.

Ulaz:

(Ulazni podaci se učitavaju iz datoteke prevara.in.) U prvom redu ulazne datoteke nalazi se prirodan broj n ≤ 10⁵ - broj karata u špilu. Sledeći red sadrži n prirodnih brojeva a_i - vrednosti karata (a_i≤ 200). Karte su date u redosledu od dna do vrha špila.

Izlaz:

(Izlazni podaci se ispisuju u datoteku prevara.out.) U prvom i jedinom redu izlazne datoteke ispisati dva broja razdvojena razmakom - maksimalan broj poena koje Mika može osvojiti nekim sečenjem i broj načina na koji on to može postići, redom.

Primer 1:

5
2 3 4 5 1

9 2

Objašnjenje.

Ako Mika preseqe posle treće ili posle četvrte karte (2 načina), on osvaja maksimalnih 9 poena.

Napomena.

U 10% test primera n ≤ 10³.

#include <stdlib.h>
#include <stdio.h>
#include <memory.h>

using namespace std;

const int maxN = 100100;
const int maxD = 410;
const int c = 205;
const int minBesk = -1000000000;

int a[maxN];
int n;

int up[maxN][maxD];
int down[maxN][maxD];


void ucitajPodatke() {
    freopen("prevara.in", "r", stdin);
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &(a[i]));
}

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

void resi() {
    memset(up, 0, sizeof(up));
  memset(down, 0, sizeof(down));

    for (int j = 0; j < maxD; j++)
        up[n][j] = j;
    for (int i = n - 1; i >= 0; i--)
        for (int j = 0; j < maxD; j++)
            if (j <= c)
                up[i][j] = up[i + 1][j + a[i]];
            else
                up[i][j] = up[i + 1][j - a[i]];
    for (int j = 0; j < maxD; j++)
        down[0][j] = j;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < maxD; j++) {
            if (down[i - 1][j] <= c)
                down[i][j] = down[i - 1][j] + a[i - 1];
            else
                down[i][j] = down[i - 1][j] - a[i - 1];
        }
}

void sacuvajResenje() {
    int sumaSvih = 0;
    for (int i = 0; i < n; i++)
        sumaSvih += a[i];

    int total = 0, max = -500;
    for (int i = 0; i < n; i++) {
        int td = down[i][up[i][c]] - c;
        int vrednost = (sumaSvih - td) / 2 + td;
        if (vrednost > max) {
           max = vrednost;
           total = 1;
        } else if (max == vrednost) total++;
    }
    freopen("prevara.out", "w", stdout);
    printf("%d %d\n", max, total);
}

int main() {
    ucitajPodatke();
    resi();
    sacuvajResenje();
    return 0;
}