C - 花壇の花選び 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は庭に一列に並んだ N 個の花壇を持っています。

各花壇には 1 から N までの番号が付けられており、i 番目の花壇に花を植えると、美しさ A_i が得られます。ただし、隣り合う花壇の両方に花を植えると、根が干渉し合って両方の花が枯れてしまいます。そのため、i 番目の花壇と i+1 番目の花壇の両方に花を植えることはできません（1 \leq i \leq N-1）。

高橋君は、この条件を満たすように花を植える花壇をいくつか選びます。各花壇に花を植えるかどうかは独立に決め、同じ花壇に複数回花を植えることはありません。どの花壇にも花を植えないことも許され、その場合の美しさの合計は 0 とします。

花を植えた花壇から得られる美しさの合計の最大値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、花壇の個数を表す整数 N が与えられる。
  • 2 行目には、各花壇に花を植えたときの美しさを表す N 個の整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • A_i は i 番目の花壇に花を植えたときに得られる美しさを表す。

出力

高橋君が達成できる美しさの合計の最大値を 1 行で出力せよ。

入力例 1

5
3 2 5 1 4

出力例 1

12

入力例 2

8
10 1 10 1 10 1 10 1

出力例 2

40

入力例 3

15
100 200 300 150 50 400 10 500 250 80 600 30 450 20 350

出力例 3

2700

Score : 366 pts

Problem Statement

Takahashi has N flower beds arranged in a row in his garden.

Each flower bed is numbered from 1 to N. Planting a flower in the i-th flower bed yields a beauty value of A_i. However, if flowers are planted in both of two adjacent flower beds, the roots interfere with each other and both flowers wither. Therefore, it is not allowed to plant flowers in both the i-th and (i+1)-th flower beds (1 \leq i \leq N-1).

Takahashi will select some flower beds to plant flowers in, subject to this condition. The decision of whether to plant a flower in each flower bed is made independently, and no flower bed is planted in more than once. It is also allowed to plant no flowers at all, in which case the total beauty is 0.

Find the maximum possible total beauty obtained from the flower beds in which flowers are planted.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • All inputs are integers

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N, representing the number of flower beds.
  • The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the beauty values obtained by planting a flower in each flower bed.
  • A_i represents the beauty obtained by planting a flower in the i-th flower bed.

Output

Print the maximum total beauty that Takahashi can achieve, in a single line.

Sample Input 1

5
3 2 5 1 4

Sample Output 1

12

Sample Input 2

8
10 1 10 1 10 1 10 1

Sample Output 2

40

Sample Input 3

15
100 200 300 150 50 400 10 500 250 80 600 30 450 20 350

Sample Output 3

2700