Dãy đảo dấu luân phiên

Points: 2 (partial)

Time limit: 1.0s

Memory limit: 98M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, ~~GAS32~~, GO, Haskell, Itercal, Java, kotlin, ~~LEAN~~, LISP, LUA, MONOVB, ~~Nasm~~, ~~OCAML~~, Pascal, Perl, php, PIKE, ~~prolog~~, Pypy, Python, ~~Ruby 2~~, RUST, Scala, SCM, SED, ~~SWIFT~~, TCL, ~~TUR~~, ~~V8JS~~, VB, ZIG

Toto học lập trình về dãy số và có một trò chơi như sau.

Cho dãy số nguyên $a_{1}, a_{2}, . . ., a_{n}$ bạn được chọn một giá trị bất kỳ trong dãy để lấy khỏi dãy, ngay sau khi lấy khỏi dãy thì toàn bộ các phần tử còn lại của dãy sẽ đảo dấu (tức là mỗi phần tử đều nhân với $- 1$ )

Bạn lặp lại bước trên tới khi dãy không còn phần tử nào.

Nhiệm vụ của bạn chọn cách lấy các phần tử sao cho tổng tất cả các phần tử lấy được là lớn nhất.

Input

Dòng đầu là số nguyên dương $n$ là số phần tử của dãy $(1 \leq n \leq 10^{5})$

Dòng cuối gồm các phần tử của dãy có giá trị tuyệt đối không vượt quá $10^{6}$

Output

Số nguyên duy nhất là kết quả của bài toán

Ví dụ

Input

Copy

7
-4 3 -4 6 -2 -5 0

Output

Copy

tichpx

Comments

2

Jojo123 commented on Jan. 2, 2022, 2:23 p.m.

Thầy ơi thầy mở thêm java đi ạ