Cerința

Se dă un șir cu n elemente, numere întregi, n fiind număr par. Calculați cea mai mare sumă care poate fi obținută schimbând semnul a exact n/2 elemente aflate pe poziții distincte din șirul dat.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului.

Date de ieșire

Programul va afișa pe ecran numărul S, reprezentând suma maximă determinată.

Restricții și precizări

• 1 ≤ n ≤ 1000
• elementele șirului vor fi cuprinse între -1.000.000 și 1.000.000

Exemplu:

Intrare

6
5 -2 -3 4 1 4

Ieșire

17

Explicație

Se schimbă semnul elementelor -2, -3 și 1.