彩帶村即將舉辦年度慶典，村長 BQ 要負責裝飾一條有 $N$ 盞路燈的街道。這些路燈的編號分別是 $1,2,3,\dots,N$。
BQ 要用一些彩帶裝飾這些路燈。BQ 有三種顏色的彩帶可用：紅色、綠色和藍色。考量到整體外觀的一致性，每個路燈必須被裝飾。除此之外，為了避免色彩使用過於單調，相鄰的路燈不能使用相同顏色的彩帶。
接著 BQ 要對這些裝飾後的路燈進行評分。每盞路燈的位置不同，其裝飾完成後對整體街道美感的影響也不同。第 $i \ (1 \le i \le N)$ 盞路燈對整體的評分價值為 $v_i$，代表這盞路燈被妥善裝飾後，對整體效果的正面或負面影響。
由於彩帶村村民對於顏色及搭配上的喜好，每當一盞路燈使用綠色彩帶裝飾時，該路燈的評分會是 $v_i$。反之若一盞路燈用了紅色彩帶，則它的評分會是 $-v_i$。至於藍色，因為村民們對於它沒什麼特別的感覺，因此用藍色彩帶裝飾的路燈評分會變成 0。
BQ 覺得只要整體的裝飾評分愈高，便可以吸引到愈多人來參加慶典。但因為 $N$ 可能很大，導致彩帶的配色變得太麻煩，因此 BQ 想先請你幫忙寫一筆程式，計算出這些裝飾後的路燈評分總和的最大值。
| $N$ $v_1$ $v_2$ $v_3$ $\dots$ $v_N$ |
| $ans$ |
3 5 5 5
10
10 9 -3 7 8 3 -5 -7 -9 6 4
42
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||