Description

Suppose that N number of stickers are attached in the circle form. The following figure is an example of N = 8.

스티커_hb1jty.jpg

You want to detach some of the stickers in the circle to maximize the sum of numbers written on the detached stickers. But, when detaching a sticker, stickers on both sides are useless because they are damaged.

For example, in the above figure, stickers with number 10 and 6 are useless after detaching sticker with number 14. Numbers written on the stickers are given as an array. Write a function solution to return the maximum sum when detaching stickers. Assume that the first element and the last element are connected to each other, to maintain stickers in the circle form.

Constraints
  • stickers is an array containing the numbers written on stickers attached in the circle form in turn, its length("N") is less than 100,000.
  • Each element of stickers is a number written on each sticker, and it is natural number between 1 and 100.
  • Assume that the first element and the last element are connected each other, to maintain stickers in the circle form.

Examples
sticker answer
[14, 6, 5, 11, 3, 9, 2, 10] 36
[1, 3, 2, 5, 4] 8

Example #1
The sum of numbers is maximized as 36 when detaching stickers with 6, 11, 9, and 10.

Example #2
The sum of numbers is maximized as 8 when detaching stickers with 3, and 5.

Result Stop
Result of [Run] or [Submit] will be displayed here