2-6 F. bb 與序列

F. bb 與序列
Problem ID: coloring

    某天 bb 拿到了一個序列，這個序列裡面的數字有正有負也有可能有零，而 bb 想用紅、綠、藍三種顏色幫這個序列上色。為了美觀，每個數字都必須被標上顏色，而且序列中任兩個相鄰的數字必須要被標上不同的顏色。

    由於 bb 喜歡綠色且討厭紅色，他覺得這個序列上色之後的價值是標上綠色的數字的總和扣掉標上紅色的數字的總和。

    請問在滿足上述的條件下，這個序列上色後價值可以變成多高呢？

Input

輸入的第一行有一個正整數 N，代表序列的長度。

第二行有 N 個以空格分開的整數 v1, v2, . . . vN，代表序列依序的數值。

• 1 ≤ N ≤ 106
• -1000 ≤ vi ≤ 1000

Output

輸出只有一行，代表上色之後這個序列的最高可能價值。