Laiko ribojimas: 1s

Atminties ribojimas: 128MB

Duomenų failas: min_max_sandauga.in

Rezultatų failas: min_max_sandauga.out

Jei norite pateikti savo sprendimą - prisijunkite.

Minimumų ir maksimumų sandauga

Ši užduotis bus labai lengva... Bent jau trumpa :) Jums duotas natūraliųjų skaičių masyvas A sudarytas iš N elementų Jums reikės apskaičiuoti išraiškos rezultatą:

\\prod|min(A[i:j])-max(A[i:j])|,\\foralli,j\\leqN\\wedgei<j

Kitaip tariant reikia sudaugint visų masyvo nuoseklių posekių (turinčių daugiau nei 1 elementą) maksimalaus ir minimauls elemento skirtumus.

Kad užduotis būtų dar lengvesnė, visi testai išskyrus pirmąjį bus generuoti atsitiktinai.

Pradiniai duomenys

Skaičius 2\\leqN\\leq100000 - masyvo dysis. Toliau seka N eilučių nurodančių masyvo elementus 0\\leqa_i\\leq1000000000.

Rezultatai

Nurodytos išraiškos rezultatas moduliu 1000000007.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
3
1 5 8
 
84