{"raw_statement":[{"iden":"problem statement","content":"Takahashi is with $N$ animals. The $N$ animals are called Animal $1$, Animal $2$, $\\ldots$, Animal $N$.\nTakahashi will perform the following $N$ kinds of action. Each action can be performed any number of (possibly zero) times.\n\n*   Pay $A_1$ yen (the currency in Japan) to feed Animals $1$ and $2$.\n*   Pay $A_2$ yen to feed Animals $2$ and $3$.\n*   Pay $A_3$ yen to feed Animals $3$ and $4$.\n*   $\\cdots$\n*   Pay $A_i$ yen to feed Animals $i$ and $(i+1)$.\n*   $\\cdots$\n*   Pay $A_{N-2}$ yen to feed Animals $(N-2)$ and $(N-1)$.\n*   Pay $A_{N-1}$ yen to feed Animals $(N-1)$ and $N$.\n*   Pay $A_N$ yen to feed Animals $N$ and $1$.\n\nNote that the $N$\\-th action above feeds \"Animals $N$ and $1$.\"\nPrint the minimum possible total cost to feed every animal at least once."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 3 \\times 10^5$\n*   $1 \\leq A_i \\leq 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\ldots$ $A_N$"},{"iden":"sample input 1","content":"5\n2 5 3 2 5"},{"iden":"sample output 1","content":"7\n\nIf Takahashi performs the $1$\\-st, $3$\\-rd, and $4$\\-th actions once each, Animals $1$, $2$, $3$, $4$, and $5$ are fed once, once, once, twice, once, respectively, so every animal is fed at least once. The total cost to do so is $A_1 + A_3 + A_4 = 2 + 3 + 2 = 7$ yen, which is the minimum possible."},{"iden":"sample input 2","content":"20\n29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62"},{"iden":"sample output 2","content":"426"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}