Fie un șir a = a
1
, a
2
, …, a
N
de numere naturale, nu neapărat distincte, cuprinse între 1
și N
. Fie de asemenea două numere naturale x
și y
. Se definește operația transform(i)
astfel: se determină valoarea w = 1 + (x * i + y * a
i
) mod N
, apoi toate elementele egale cu a
i
din secvența a
i
, a
i+1
, …, a
N
își modifică valoarea în w
. De exemplu, pentru șirul a=1, 7, 1, 7, 3, 4, 7
, x = 4
, y = 5
, operația transform(4)
înseamnă că w = 1+(4*4+5*7) mod 7 = 3
, deci șirul devine 1
, 7
, 1
, 3
, 3
, 4
, 3
(toate elementele de la poziția 4
la 7
și egale cu 7
s-au modificat în 3
). După fiecare operație de tip transform se calculează suma elementelor șirului obținut.
Cerința
Să se determine suma maximă care s-a obținut în șirul a
efectuând pe rând asupra șirului operațiile transform(1)
, transform(2)
, …, transform(N)
.
Date de intrare
Fișierul de intrare transform.in
conține pe prima linie numerele naturale N
, x
și y
. Pe linia a doua se găsesc, separate prin spațiu, elementele șirului a
.
Date de ieșire
Fișierul de ieșire transform.out
va conține pe prima linie un singur număr natural reprezentând suma maximă obținută.
Restricții și precizări
3 ≤ N ≤ 256.000
1 ≤ x, y ≤ N
Exemplu:
transform.in
7 4 5 1 7 1 7 3 4 7
transform.out
35
Explicație
După transform(1)
, în care w = 3, șirul devine 3
, 7
, 3
, 7
, 3
, 4
, 7
care are suma 34
.
După transform(2)
, în care w = 2
, șirul devine 3
, 2
, 3
, 2
, 3
, 4
, 2
care are suma 19
.
După transform(3)
, în care w = 7
, șirul devine 3
, 2
, 7
, 2
, 7
, 4
, 2
care are suma 27
.
După transform(4)
, în care w = 6
, șirul devine 3
, 2
, 7
, 6
, 7
, 4
, 6
care are suma 35
.
După transform(5)
, în care w = 7
, șirul devine 3
, 2
, 7
, 6
, 7
, 4
, 6
care are suma 35
.
După transform(6)
, în care w = 3
, șirul devine 3
, 2
, 7
, 6
, 7
, 3
, 6
care are suma 34
.
După transform(7)
, în care w = 3
, șirul devine 3
, 2
, 7
, 6
, 7
, 3
, 3
care are suma 31
.
Suma maximă care s-a obținut este 35
.