Podciągi zmienne
Limit pamięci: 32 MB
W danym ciągu poszukujemy podciągów zmiennych.
Podciąg ciągu otrzymujemy, usuwając z niego dowolną liczbę wyrazów (potencjalnie zero).
Formalnie, podciągiem ciągu jest dowolny ciąg
, przy czym .
Natomiast podciąg zmienny charakteryzuje się tym, że jego każde dwa
kolejne wyrazy są różne.
Dla przykładu, ciąg jest podciągiem zmiennym
ciągu .
Zastanawiamy się, ile różnych i niepustych podciągów zmiennych zawiera dany ciąg.
Podciągi uważamy za różne, jeśli zostały wybrane z innych zestawów
pozycji w ciągu .
Przykładowo, ciąg zawiera dwa różne podciągi zmienne
postaci .
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba
naturalna (), oznaczająca długość ciągu .
Drugi wiersz zawiera liczb całkowitych
().
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia Twój program
powinien wypisać jedną liczbę całkowitą:
resztę z dzielenia przez liczby niepustych podciągów
zmiennych ciągu podanego na wejściu.
Przykład
Dla danych wejściowych:
4
1 2 1 1
poprawną odpowiedzią jest:
9
Wyjaśnienie do przykładu:
Szukanymi podciągami ciągu są:
- - wliczany trzykrotnie,
- - wliczany raz,
- - wliczany raz,
- - wliczany dwukrotnie oraz
- - wliczany dwukrotnie.
Autor zadania: Jakub Radoszewski.