INF = 1i64 << 60 n = read_line.to_i a = read_line.split.map(&.to_i64) dp = [-INF, -INF] n.times do |i| if dp[0] == -INF && dp[1] == -INF dp[0] = -a[i] elsif dp[1] == -INF dp[0], dp[1] = {dp[0], -a[i]}.max, dp[0] + a[i] else dp[0], dp[1] = {dp[0], dp[1] - a[i], -a[i]}.max, {dp[1], dp[0] + a[i]}.max end end puts dp.max