배열의 특징

길이가 $N$인 정수 배열 $A = A_1, A_2, \dots, A_N$이 주어진다. 배열의 특징 $C$는 $C = \sum_{i=1}^{N} A_i \times i$로 정의된다.

배열에서 원소 하나를 골라 아무 위치로 이동시킬 수 있다. 옮길 자리는 배열의 맨 앞이어도 되고 맨 뒤여도 되며, 원래 자리여도 된다. 원소를 빼내면 그보다 뒤에 있던 원소가 한 칸씩 앞으로 당겨지고, 새 자리에 끼워 넣으면 그 자리부터 뒤에 있는 원소가 한 칸씩 뒤로 밀린다. 이동은 한 번만 한다.

원소를 하나 옮긴 뒤 얻을 수 있는 $C$의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 $N$이 주어진다. ($2 \le N \le 200{,}000$)

둘째 줄에 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($|A_i| \le 1{,}000{,}000$)

원소를 하나 옮긴 뒤 $C$의 최댓값을 한 줄에 출력한다.