2654 - Sort All

Enunt

Pentru un șir de numere A

se definește următoarea funcție de cost: f(A)=1⋅v1+2⋅v2+…+k⋅vk

, unde [v1,v2,…,vk]

sunt valorile distincte ale lui A

, ordonate crescător.

Cerinţa

Fiind dat un șir de N numere naturale A, să se calculeze suma aplicării funcției f pe toate subsecvențele lui A (i.e. suma după (1 ≤ i ≤ j ≤ N) din f(A[i...j]), unde A[i…j] este subsecvența de la i la j).

Date de intrare

Fișierul sortall.in conține pe prima linie numărul natural N. Linia a doua conține N numere naturale separate prin spațiu, reprezentând elementele șirului A.

Date de ieșire

Fișierul sortall.out va conține răspunsul modulo 1 000 000 007.

Restricţii şi precizări

• 1 ≤ N ≤ 50 000
• 1 ≤ Vi ≤ N
• Pentru 10 puncte 1 ≤ N ≤ 100
• Pentru alte 15 puncte 1 ≤ N ≤ 1000
• Pentru alte 15 puncte 1 ≤ N ≤ 5000
• Pentru alte 20 de puncte se garanteză că valorile din șir sunt distincte

Exemplul 1

sortall.in

 3
 1 3 2

sortall.out

 35

Exemplul 2

sortall.in

 8
 4 3 4 4 7 1 2 1

sortall.out

 864

Rezolvare

MOD = 1000000007

def solve(N, A):
    freq = {}
    total_sum = 0

    for i in range(N):
        curr_sum = 0

        for num in freq:
            if num <= A[i]:
                curr_sum += (i - freq[num] + 1) * num * (freq[num] - freq.get(num - 1, 0))
                curr_sum %= MOD

        total_sum += curr_sum
        total_sum %= MOD

        freq[A[i]] = i + 1

    return total_sum

def main():
    with open("sortall.in", "r") as fin:
        N = int(fin.readline())
        A = list(map(int, fin.readline().split()))

    result = solve(N, A)

    with open("sortall.out", "w") as fout:
        fout.write(str(result) + "\n")

if __name__ == "__main__":
    main()