Највећи тежински збир после цикличног померања

Дат је низ \(a\) целих бројева дужине \(n\). Дозвољена је операција цикличног померања тј. ротације низа улево за једно место, операцију можемо понављати произвољан број пута. Написати програм којим се израчунава највећа вредност тежинског збира

\[0 \cdot a_0 + 1 \cdot a_1 + 2\cdot a_2 + 3 \cdot a_3 + \ldots + (n-1) \cdot a_{n-1},\]

по модулу 1234567 у трансформисаном низу.

Улаз

У првој линији стандардног улаза налази се природан број \(n\) (\(1 \leq n \leq 50000\)). У следећих \(n\) линија налазе се редом елемeнти низа \(a\) (цели бројеви из интервала \([0, 100]\)).

Излаз

На стандардном излазу у једној линији приказати највећу вредност тежинског збира.

Пример

Улаз

3
5
4
1

Излаз

13

Објашњење

Највећи збир се добија након ротације за два места улево (низ је тада 154).