Farmer John 的牛想像最喜歡的童謠中的牛一樣跳過月亮。可惜牛不會跳。
當地巫醫調製 $P$ 份藥水（$1 \le P \le 150{,}000$）幫助牛跳躍。必須嚴格按調製順序服用，但可跳過部分。
每份藥水有增強跳躍能力的「強度」（$1 \le strength \le 500$）。奇數時間步服藥增加跳躍高度，偶數時間步則降低高度。服藥前跳躍能力當然為0。
每份不可服用兩次；一旦開始服藥，從時間1起每個時間步必須服用一份。每輪可跳過一份或多份藥水。
決定服用哪些藥水以獲得最高跳躍高度。
輸入格式
- 第 $1$ 行：整數 $P$。
- 第 $2..P+1$ 行：每行含一整數，表示藥水強度。第2行是第一份強度，第3行是第二份，依此類推。
輸出格式
- 第 $1$ 行：一整數，表示最大可能跳躍高度。
範例
輸入格式 1
8 7 2 1 8 4 3 5 6
輸出格式 1
17