trojke

Profesor matematike je postavio Dragan?etu slede?i zadatak. Na osnovu datog niza brojeva a[1], a[2], ..., a[n], Dragan?e treba da za svaku trojku indeksa (i, j, k), gde je 1 ? i < j < k ? n, napiše na tabli najve?i od brojeva ai, aj i ak. Zatim treba da izra?una ostatak koji daje zbir svih brojeva koji su napisani na tabli pri deljenju sa 10007. Profesor je obe?ao Dragan?etu peticu za kraj školske godine, ako dobije ta?no rešenje pre kraja ?asa. Pomozite Dragan?etu da što brže dobije ta?an rezultat.
<br><br>
Ulaz:
<br><br>
(Ulazni podaci se citaju sa standardnog ulaza) U prvom redu nalazi se broj n (3 ? n ? 30000). U slede?ih n redova se nalaze celi brojevi a[1], a[2], ..., a[n], pri chemu je -100000 ? a[i] ? 100000.
<br><br>
Izlaz:
<br><br>
(Izlazne podatke ispisati na standardni izlaz) U prvom i jedinom redu ispisati sumu brojeva napisanih na tabli po modulu 10007.
<br><br>
Primeri:<br><br>
Ulaz:<br>
4<br>
3<br>
-1<br>
2<br>
2<br><br>
Izlaz:<br>
11<br><br>

Objašnjenje.<br>
Sve trojke niza brojeva su: (3, -1, 2), (3, -1, 2), (3, 2, 2), (-1, 2, 2). Na tabli su napisani brojevi 3, 3, 3, 2, pa je rešenje u ovom slu?aju 11.<br><br>

Ulaz:<br>
6<br>
8<br>
-10<br>
4<br>
5<br>
2<br>
6<br>
<br>
Izlaz:<br>
135