Fie un şir a = a1, a2, ..., aN 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 · ai) mod N, apoi toate elementele egale cu ai din secvenţa ai, ai+1, ..., aN îş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ţă
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 y. Pe linia a doua se găsesc, separate prin spaţii, 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
3<= N <= 256 000
1 <= x, y <= N
Exemplu
transform.in
transform.out
Explicaţii
7 4 5
1 7 1 7 3 4 7
35
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.