Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P203PROA - Segment Three

Cho một dãy số có n phần tử a_1, a_2, .., a_n. (-1e6 <= a_i <= 1e6)

Định nghĩa hàm Segment Three ST(l, r, k) như sau:

  1. 1 <= l <= r <= n <= 2e5 , k = r – l + 1
  2. s_1 = a_l, s_2 = a_(l+1), … s_k = a_r
  3. ST (l, r, k) = 1 * s_1 + 2 * s_2 + … + k * s_k

Nhiệm vụ của bạn là tìm giá trị lớn nhất có thể của hàm ST

Input

Dòng đầu tiên chứa số nguyên n

Dòng tiếp theo là n số nguyên của dãy số

Output

Một số duy nhất là kết quả của bài toán.

Example

Input

Output

4

-1 2 3 -5

12

 

Input

Output

5

-3 -2 1 -2 -3

1


Được gửi lên bởi:adm
Ngày:2020-08-29
Thời gian chạy:1s
Giới hạn mã nguồn:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM64 CPP CPP14 JAVA PYTHON PYTHON3

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.