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

Дат је низ $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).