Dat je niz brojeva A = (a₁, ..., a_N). Posmatrajmo skup svih suma uzasotpnih članova S = {a_i + ... + a_j | 1 ≤ i ≤ j ≤ N}.

Ispisati vrednost iz skupa S koja se najčešće pojavljuje, kao i koliko puta se pojavljuje. U slučaju da ima više takvih, ispisati onu čija je vrednost najveća.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza.) U prvom redu standardnog ulaza nalazi se prirodan broj N (1 ≤ N ≤ 3000). U sledećem redu nalazi se N prirodnih brojeva, redom a₁ , ..., a_N, svaki iz intervala [0, 3000].

Izlaz.

(Izlazne podatke ispisati na standardan izlaz.) U prvi i jedini red standardog izlaza ispisati dva prirodna broja, koji redom predstavljaju, broj koji se najšeće pojavljuje u skupu S, i koliko puta se pojavljuje. U slučaju da postoji više takvih brojeva, ispisati onaj koji ima najveću vrednost.

Ograničenja.

U 30% test primera će biti 1 ≤ N ≤ 100.

Primer 1.

3
1 2 3

3 2

Objašnjenje.

Skup S = {1, 1 + 2, 1 + 2 + 3, 2, 2 + 3, 3} = {1, 3, 6, 2, 5, 3}.

Primer 2.

8
17 13 17 13 5 6 5 6

30 3

Objašnjenje.

Primetimo da se i suma 11 pojavljuje 3 puta, ali je 30 veća suma.

#include <iostream>
#include <cstdio>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)
#define SET(__set, val) memset(__set, val, sizeof(__set))
#define FOR(__i, __n) ffor (__i, 0, __n)

using namespace std;

int cnt[9000001], sum[3001];

int main(){
  int n, val;
  scanf("%d", &n);
  sum[0] = 0;
  FOR (i, n){
    scanf("%d", &val);
    sum[i + 1] = sum[i] + val;
  }
  
  SET(cnt, 0);
  
  ffor (i, 1, n + 1){
    val = sum[i];
    FOR (j, i)
      cnt[val - sum[j]]++;
  }
  int mm = 0, ret = -1;
  
  FOR (i, 9000001)
    if (cnt[i] >= mm){
      mm = cnt[i];
      ret = i;
    }
    
  printf("%d %d\n", ret, mm);
    
  return 0;
}