Slabě doleva vychýlené úseky posloupnosti

Zadání

Je dána posloupnost P celých nezáporných čísel, v níž se žádná hodnota nevyskytuje vyskytuje více než jednou.
P = a₁, a₂, …, a_N, kde N ≥ 2.
Úsek délky L posloupnosti P je každá podposloupnost a_k, a_k+1, …, a_k+L−1, kde 1 ≤ k; 2 ≤ L; k+L−1 ≤ N.
Úsek nazveme slabě doleva vychýlený, pokud index minimální hodnoty v tomto úseku je menší než index maximální hodnoty v tomto úseku, to jest minimální ze všech hodnot v úseku se nachází vlevo (ne nutně v bezprostředním sousedství) od maximální ze všech hodnot v tomto úseku.

Posloupnost P je dána takto:
a₁ = S,
a_i+1 = (754043 * a_i + 500009) mod M, pro 1 ≤ i < N.

Hodnoty S, M jsou daná celá kladná čísla.

Úkolem je najít počet slabě doleva vychýlených úseků délky L v posloupnosti P.

Vstup

Na vstupu je jeden řádek se čtyřmi čísly představujícími postupně hodnoty N, L, S, M. Čísla jsou oddělena mezerou.
Platí 2 ≤ N ≤ 1000000, 2 ≤ L ≤ N, 2 ≤ S ≤ 1000000, 2 ≤ M ≤ 2000000.

Výstup

Na výstupu je jediný řádek s jediným číslem představujícím počet slabě doleva vychýlených úseků délky L v dané posloupnosti.

Poznámka

Je zřejmé, že díky dané maximální délce posloupnosti a délce zkoumaných úseků není účelné uvažovat o algoritmu s kvadratickou asymptotickou složitostí vzhledem k N nebo L.

Příklady

Příklad 1

Vstup

6 3 11 29

Výstup

Posloupnost P je v tomto případě:

11 0 20 10 15 27

Příklad 2

Vstup

7 5 11 23

Výstup

Posloupnost P je v tomto případě:

11 18 3 22 1 0 12

Příklad 3

Vstup

1000000 500000 519217 1000003

Výstup

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data