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 učitavaju sa standardnog ulaza) 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:

(Izlazni podaci se ispisuju na standardni izlaz) 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

Objašnjenje.

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