3691 - crescator2

Fie un șir a de N numere întregi. Trebuie construit un nou șir b(tot cu N elemente) astfel:

• dacă , atunci
• dacă , atunci  poate avea orice valoare strict pozitivă
• dacă , atunci  poate avea orice valoare strict pozitivă cu excepția lui

Se garantează că  și au valori strict pozitive și între oricare două valori strict pozitive se va afla cel mult una strict negativă.

Cerinta

Știindu-se șirul a, să se calculeze numărul de moduri de a forma șirul b astfel încât acesta să fie crescător (nu neapărat strict). Deoarece acest număr poate fi foarte mare, se va afișa doar restul împărțirii la 1.000.000 007.

Date de intrare

Fișierul de intrare crescator.in conține pe prima linie un număr natural N și pe cea de-a doua N numere întregi separate prin câte un spațiu.

Date de iesire

Fișierul de ieșire crescator.out conține pe singura sa linie numărul cerut modulo 1.000.000 007

Restricții și precizări

• 1 ≤ N ≤ 300.000
• Pentru 35 de puncte, 1 ≤ N ≤ 1000 și
• Pentru alte 20 de puncte,

Exemplu:

crescator.in

6
1 0 3 0 -4 5

crescator.out

12

Explicație

Cele 12 șiruri crescătoare b sunt: 1 1 3 3 3 5, 1 1 3 3 5 5, 1 1 3 4 5 5, 1 1 3 5 5 5, 1 2 3 3 3 5, 1 2 3 3 5 5, 1 2 3 4 5 5, 1 2 3 5 5 5, 1 3 3 3 3 5, 1 3 3 3 5 5, 1 3 3 4 5 5, 1 3 3 5 5 5.

Rezolvare

def sort_and_count_frequencies(numbers):
    sorted_numbers = sorted(numbers)

    element_counts = {}

    for number in sorted_numbers:
        if number in element_counts:
            element_counts[number] += 1
        else:
            element_counts[number] = 1

    return element_counts

def main():
    numbers = list(map(int, input().split()))

    element_counts = sort_and_count_frequencies(numbers)

    for number, count in element_counts.items():
        print(f"{number}: {count}")

if __name__ == "__main__":
    main()