Cone Coloring
Description
Cassidy runs an unorthodox ice cream shop! Each day before the store opens she lines up all of her food coloring dyes of various colors and shades in order to paint each waffle cone with a unique design. In particular, Cassidy has exactly $N$ dyes of various colors. Each of the dyes has a beauty rating assigned by the regular customers, with the beauty rating of the $i$th color represented by a positive integer $b_i$.
Today Cassidy is feeling especially creative. She would like to paint one of the cones in the most beautiful way possible! The beauty score of a cone is calculated as the sum of the beauty ratings of the dyes used to paint it. Moreover, Cassidy cannot use two dyes to paint the cones if they are directly adjacent to each other in the lineup of colors.
Based on the ordering of her dyes and their respective beauty ratings, can you help Cassidy calculate the most beautiful (in terms of beauty score) cone that she can paint?
The input will begin with a line containing a single integer, $N\ (1 \leq N \leq 10^5)$, representing the number of dyes that Cassidy has to paint with in the ice cream shop. The second and final line will contain exactly $N$ space-separated positive integers, $b_i\ (1 \leq b_i \leq 10^9)$, the $i$th of which represents the beauty rating of the $i$th dye in Cassidy's lineup of dyes.
The output should consist of a single line containing a single integer representing the highest beauty score Cassidy can attain for a single cone. Note again that the only restriction on the dyes Cassidy can use is that they may not be adjacent in her lineup.
Input
The input will begin with a line containing a single integer, $N\ (1 \leq N \leq 10^5)$, representing the number of dyes that Cassidy has to paint with in the ice cream shop. The second and final line will contain exactly $N$ space-separated positive integers, $b_i\ (1 \leq b_i \leq 10^9)$, the $i$th of which represents the beauty rating of the $i$th dye in Cassidy's lineup of dyes.
Output
The output should consist of a single line containing a single integer representing the highest beauty score Cassidy can attain for a single cone. Note again that the only restriction on the dyes Cassidy can use is that they may not be adjacent in her lineup.
5
5 10 9 10 7
21