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


Submit solution

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 \le n \le 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

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

Output

20
tichpx

Comments


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

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