Niz brojeva je palindromski, ako se čita isto i sa leve i sa desne strane. Na primer, nizovi {1, 5, 1} i {10, 9, 9, 10} su palindromski, dok {1, 2, 3, 1} i {20, 2} nisu palindromski.

Na početku je dat niz prirodnih brojeva a dužine n. U jednom koraku dozvoljeno je zameniti dva susedna broja njihovom sumom (obrisati dva susedna broja a[i] i a[i + 1] i na njihovom mestu upisati a[i] + a[i + 1]). Odrediti najveću moguću dužinu palindromskog niza, koji se može dobiti primenom ove operacije proizvoljan broj puta.

Ulaz:

(Ulazni podaci se nalaze u datoteci pniz.in) U prvom redu se nalazi prirodan broj n (1 ≤ n ≤ 100.000). U drugom redu se nalaze n prirodnih brojeva a[i] (1 ≤ a[i] ≤ 10.000), koji predstavljaju elemente niza a.

Izlaz:

(Izlazne podatke upisati u datoteku pniz.out) U prvom i jedinom redu ispisati jedan prirodan broj koji predstavlja najveću dužinu palindromskog niza koji se može dobiti od polaznog niza.

Primer:

6
10 10 10 20 20 30

4

Objašnjenje.

Zamenimo prva dva broja i dobijamo niz {20, 10, 20, 20, 30}. Zatim menjamo opet prva dva broja i dobijamo palindromski niz {30, 20, 20, 30} dužine četiri.

Primer:

5
1 2 3 4 5

1

Jedini palindromski niz koji možemo dobiti je {15}.

#include<stdio.h>

#define MAXN 100001

int n, sol;
int a [MAXN];

int mmain ()
{
  FILE *in = fopen ("palindrom.in", "r");
  fscanf (in, "%d", &n);
  for (int i = 0; i < n; i++)
    fscanf (in, "%d", &a [i]);
  fclose (in);

  int left = 0;
  int right = n - 1;
  while (left < right)
  {
    if (a [left] < a [right])
    {
      a [left + 1] += a [left];
      left++;
    }
    else if (a [left] > a [right])
    {
      a [right - 1] += a [right];
      right--;
    }
    else
    {
      sol += 2;
      left++;
      right--;
    }
  }
  if (left == right)
    sol++;

  FILE *out = fopen ("palindrom.out", "w");
  fprintf (out, "%ld\n", sol);
  fclose (out);

  return 0;
}