evantai

Lui Algorel îi plac mult șirurile de numere naturale cu proprietăți cât mai ciudate. Căutând astfel de ciudățenii ale informaticii, a găsit printr-o carte prăfuită de vreme un nou tip de șir denumit evantai. Un evantai este un șir cu un număr par de termeni, $E_1 \ E_2 \dots E_{2 \cdot K}$, cu următoarea proprietate:

$E_1 + E_{2 \cdot K} > E_2 + E_{2 \cdot K - 1} > \dots > E_K + E_{K+1}$

Cerință

Fiind dat un șir de numere naturale distincte $A_1 A_2 \dots A_N$, Algorel vrea să afle câte subșiruri ale acestuia sunt evantaie.

Date de intrare

Prima linie a fișierului evantai.in conține numărul întreg $N$, reprezentând numărul de elemente ale șirului. Următoarele $N$ linii conțin, în ordine, elementele șirului $A$.

Date de ieșire

Pe prima linie a fișierului evantai.out se va afla un singur număr întreg $C$, reprezentând numărul de subșiruri evantai. Rezultatul va fi afișat modulo $30 \ 103$.

Restricții și precizări

• $2 \leq N \leq 700$
• Elementele șirului sunt numere intregi distincte cuprinse între $1$ și $1 \ 000$
• Prin subșir se ințelege orice inșiruire de termeni $A_{i_1} \ A_{i_2} \dots A_{i_k}$ astfel încât $i_1 < i_2 < \dots < i_k$

Exemplu

evantai.in

4
1
2
3
6

evantai.out

7