Teleport
TopCoder TCO2019, Round 1B
Time Limit: 1.3s, Memory Limit: 64MiB
Ели играе следната компютърна игра. Една над друга има N платформи, всяка с различна височина A1, A2, ..., AN. Момичето управлява "герой", който се придвижва от платформа на платформа. На всяка платформа има по една монета, която героят събира когато отиде там за пръв път, добавяйки я към резултата на играча. Повторно посещаване на платформа не увеличава резултата на играча, тъй като монетата от платформата вече е взета.

В началото героят на момичето започва от някоя от платформите по нейн избор (взимайки монетата там). След това Ели може да ползва специално устройство – телепортатор – който мести героя й по вертикала. Ако текущата височина на платформата е X, то височината, на която отива героят на момичето, е Y = (X * P + Q) % M, където P, Q, и M са цели числа, известни на играча. Ако на новата височина Y има платформа, героят отива там. В противен случай почва да пада, докато стигне най-близката надолу. Ако такава няма, героят умира и играта свършва.

Очевидно, момичето може да събере поне една монета (от началната платформа), но при добър избор на начална платформа е възможно и повече. Помогнете на Ели, като намерите колко най-много монети могат да бъдат събрани.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N, P, Q, и M – съответно броя платформи и параметрите на телепортатора. На следващия ред ще бъдат зададени N цели числа A1, A2, ..., AN – височините на платформите. Гарантирано е, че всички височини са различни.
Изход
На стандартния изход изведете едно цяло число – максималния брой монети, които могат да бъдат събрани при оптимален избор на начална платформа.
Ограничения
  • 1 ≤ N ≤ 10,000
  • 0 ≤ P, Q < M ≤ 1,000,000,007
  • 0 ≤ Ai < M
Примерен Вход Примерен Изход
11 7 13 23 9 1 3 14 17 22 15 11 12 6 19 6
8 15 28 43 17 23 32 24 12 37 10 34 4
Оптимално е да се започне от платформата с височина 15, като така височините са: 15 -> 3 -> 11 -> [21] -> 19 -> [8] -> 6 -> 9 -> [7] -> 6 ... С [Y] сме отбелязали височина, на която няма платформа и героят пада надолу до най-близката такава. При второто посещение на 6 (и всички след това) играчът не получава нови монети.
Във втория пример оптимални стратегии са 32 -> [35] -> 34 -> [22] -> 17 -> [25] -> 24 -> [1] или 12 -> [36] -> 34 -> [22] -> 17 -> [25] -> 24 -> [1]. Макар и героят да умира след последната телепортация, така се печелят най-много монети.
Мрън!