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.|

P191PROF - Problem F - Tổng các đoạn

Bạn được cho một mảng số nguyên gồm n phần tử (chỉ số trong mảng được đánh bắt đầu từ 0). Gọi sum(l, r) là tổng các phần tử từ vị trí l đến vị trí r - 1 của mảng (0 ≤ l ≤ r ≤ n).

Đặt S = sum(0, d0) - sum(d0, d1) + sum(d1, d2) - sum(d2, n). Trong đó 0 ≤ d0 ≤ d1 ≤ d2 ≤ n. Bạn hãy tìm các giá trị của d0, d1, d2 để S đạt ra trị lớn nhất và in ra giá trị lớn nhất của S.

Input

  • Dòng đầu tiên chứa số nguyên n duy nhất (1 ≤ n ≤ 5000) - số phần tử của mảng.
  • Dòng tiếp theo gồm n số nguyên ai (-109 ≤ ai ≤ 109) - các phần tử của mảng.

Output

In ra một số nguyên duy nhât là giá trị lớn nhất của S.

Example

Input:
4
3 1 -2  4

Output:
10

Được gửi lên bởi:adm
Ngày:2019-02-15
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

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