Državno natjecanje 2020. godine za 1. i 2. razred Srednje Škole - 4. zadatak

n štapića raznih duljina ciklički su spojeni u vrhovima tako da čine mnogokut. Savijanjem mnogokuta u vrhovima (pri čemu se mijenjaju veličine kutova, ali ne i duljine stranica) možemo dobiti razne oblike. Primjerice, od kvadrata možemo dobiti romb i obrnuto, a neke susjedne štapiće možemo i "poravnati" tako da leže na istom pravcu (zatvaraju ispruženi kut) čime dobivamo jednostavnije oblike.

Neki od oblika koje tako možemo dobiti su trokuti, a u ovom zadatku zanima nas broj načina na koje možemo dobiti takav trokut savijanjem mnogokuta, tj. biranjem triju vrhova koji će postati vrhovi trokuta. Slika ilustrira moguća savijanja iz prvih dvaju probnih primjera.

Napomene. Nije važno jesu li neki od dobivenih trokuta sukladni; svako ispravno savijanje u smislu odabira odgovarajuće trojke vrhova mnogokuta brojimo kao jedan trokut. Trokut ne smije biti degeneriran, tj. mora zatvarati površinu strogo veću od nula.

ULAZNI PODACI

U prvom je retku prirodan broj n (1 ≤ n ≤ 1 000 000).

Drugi redak sadrži n prirodnih brojeva između 1 i 10^9, duljine štapića redom kojim su spojeni (posljednji je spojen s prvim). Duljine će biti takve da je opisano spajanje moguće.

IZLAZNI PODACI

U jedini redak ispišite traženi broj načina.

PRIMJERI TEST PODATAKA

ulaz

4
3 5 6 7

izlaz

2

ulaz

5
5 5 5 5 5

izlaz

5

ulaz

4
1 1 1 1

izlaz

0