W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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 .
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba naturalna (), oznaczająca długość ciągu . Drugi wiersz zawiera liczb całkowitych ().
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.
Dla danych wejściowych:
4 1 2 1 1
poprawną odpowiedzią jest:
9
Wyjaśnienie do przykładu: Szukanymi podciągami ciągu są:
Autor zadania: Jakub Radoszewski.