CF1038D.Slime

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There are nn slimes in a row. Each slime has an integer value (possibly negative or zero) associated with it.

Any slime can eat its adjacent slime (the closest slime to its left or to its right, assuming that this slime exists).

When a slime with a value xx eats a slime with a value yy , the eaten slime disappears, and the value of the remaining slime changes to xyx - y .

The slimes will eat each other until there is only one slime left.

Find the maximum possible value of the last slime.

输入格式

The first line of the input contains an integer nn ( 1n5000001 \le n \le 500\,000 ) denoting the number of slimes.

The next line contains nn integers aia_i ( 109ai109-10^9 \le a_i \le 10^9 ), where aia_i is the value of ii -th slime.

输出格式

Print an only integer — the maximum possible value of the last slime.

输入输出样例

  • 输入#1

    4
    2 1 2 1
    

    输出#1

    4
  • 输入#2

    5
    0 -1 -1 -1 -1
    

    输出#2

    4

说明/提示

In the first example, a possible way of getting the last slime with value 44 is:

  • Second slime eats the third slime, the row now contains slimes 2,1,12, -1, 1
  • Second slime eats the third slime, the row now contains slimes 2,22, -2
  • First slime eats the second slime, the row now contains 44

In the second example, the first slime can keep eating slimes to its right to end up with a value of 44 .

首页