Se consideră un șir de N numere naturale. Numim rectangle-sequence orice secvență continuă din șir (formată din elemente situate pe poziții consecutive) care conține cel puțin două elemente. Fiecare rectangle-sequence este caracterizată de un dreptunghi cu lungimile laturilor egale cu cele mai mari două elemente din cadrul ei.

Cerința

Să se calculeze restul împărțirii sumei ariilor dreptunghiurilor ce caracterizează toate rectangle-sequences din șir la numărul 1.000.000.007.

Date de intrare

Prima linie contine numărul natural nenul N, reprezentând numărul elementelor din șir, iar linia a doua conține, separate prin câte un spațiu, cele N elemente. Întrucât volumul datelor de intrare este foarte mare, vă recomandăm, în cazul în care folosiți pentru citire biblioteca iostream din standardul C++, să adaugați la începutul funcției main urmatoarele instrucțiuni:

std :: iosbase :: sync_with_stdio (false);
std :: cin.tie(0);

Date de ieșire

Ieșirea conține numărul de determinat, modulo 1.000.000.007.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000
• 1 ≤ orice element din șir 1 ≤ 1.000.000.000
• Subtask 1 (13 puncte): N ≤ 2000
• Subtask 2 (23 puncte): N ≤ 100.000 și există cel mult 100 de numere distincte în șir.
• Subtask 3 (27 puncte): N ≤ 200.000
• Subtask 4 (37 puncte): nu există restricții suplimentare

Exemplu:

Intrare

3
2 3 1

Ieșire

15

Explicație

Sunt 3 rectangle-sequences: (2; 3); (2; 3; 1); (3; 1). Ariile celor trei deptunghiuri ce le caracterizează sunt: 6, 6, 3.