Giá trị lớn nhất

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: VMAX.INP Output: VMAX.OUT

Cho dãy số nguyên dương \(A\) gồm \(N\) phần tử \(A_i\) (\(1 \le i \le N; 3 \le N \le 10^6; 1 \le A_i \le 2 \cdot 10^9\)) và biểu thức \(M = A_i - 3A_j + 2A_k\) với \(A_i, A_j, A_k\) thuộc dãy số \(A\) (\(1 \le i < j < k \le N\)).

Yêu cầu: Tìm giá trị \(M\) lớn nhất.

Input

Dòng 1: Ghi số nguyên dương \(N\).
Dòng 2: Ghi \(N\) số nguyên dương \(A_i\), mỗi số cách nhau một khoảng trống.

Output

Ghi ra một số duy nhất là giá trị \(M\) tìm được.

Example

Test 1

Input

5
8 1 2 6 3

Output

Note

Với \(i=1, j=2, k=4\), ta có \(M = A_1 - 3A_2 + 2A_4 = 8 - 3 \cdot 1 + 2 \cdot 6 = 8 - 3 + 12 = 17\).

Scoring

Có \(70\%\) số lượng bộ test tương ứng với \(3 < N \le 300; 1 \le A_i \le 65535\).
Có \(30\%\) số lượng bộ test tương ứng với \(300 < N \le 10^6; 1 \le A_i \le 2 \cdot 10^9\).

Bình luận

Tải bình luận...

Không có bình luận nào.