비즈니스 마법

$n$개의 상점이 거리를 따라 늘어서 있으며, 가까운 곳부터 멀리 있는 곳까지 1번부터 $n$번까지 번호가 붙어 있다. 지난달 상점 $k$의 순이익은 $r_k$였다. $r_k$가 양수이면 $r_k$달러의 이익을, 음수이면 $-r_k$달러의 손실을 뜻한다.

다음 달 상점들의 순이익을 바꿀 수 있는 마법이 두 종류 있다.

1. 파란 마법: 연속된 구간 $[L, R]$을 하나 고른다. $L$번 상점부터 $R$번 상점까지(양 끝 포함) 모든 상점의 순이익을 두 배로 만든다. 즉 $k \in [L, R]$이면 상점 $k$의 다음 달 순이익은 $2r_k$가 된다.
2. 초록 마법: 상점 하나를 고르고 그 상점에 마법을 건다. 그 상점의 다음 달 순이익은 지난달 순이익의 음수가 된다.

두 마법 중 어느 것도 받지 않은 상점은 다음 달에도 지난달과 같은 순이익을 낸다.

마법을 쓰는 데에는 제약이 있다. 파란 마법은 한 번만 쓸 수 있으며, 반드시 초록 마법보다 먼저 써야 한다. 파란 마법을 받은 상점에는 초록 마법을 걸 수 없다. 마법을 최적으로 썼을 때 다음 달 모든 상점 순이익 합의 최댓값을 구하라.

첫째 줄에 상점의 수 $n$이 주어진다. 둘째 줄에는 공백으로 구분된 정수 $r_1, r_2, \dots, r_n$이 주어지며, $r_k$는 지난달 상점 $k$의 순이익이다.

다음 달 모든 상점 순이익 합의 최댓값을 정수 하나로 출력한다.

• $1 \le n \le 3 \times 10^5$
• $-10^9 \le r_k \le 10^9$ ($k \in \{1, 2, \dots, n\}$)