618. Mark and Score

0

Medium

Once upon a time, there was a young boy named Jack who had a passion for playing games. One day, he discovered a new game called "Mark and Score" that had a fascinating algorithm.

The game involved an array of positive integers, and the objective was to select the smallest unmarked integer, add it to the score, and then mark the chosen element along with its two adjacent elements (if they existed). The game continued until all the elements in the array were marked, and the final score was determined by summing up all the chosen integers.

Jack was eager to try out the game. He was given an array of integers and began playing.

He played the game by selecting the smallest unmarked integer and adding it to the score until all the elements in the array were marked. At the end of the game, he calculated the final score and was thrilled with the result.

Can you calculate the final score given the array?

Input Format

The first line contains the size of the array, n. The next line contains n space-separated integers representing the elements of the array.

Output Format

Print the final score as an integer value.

Example

Input

6 2 3 5 1 3 2

Output

5

Constraints

1 <= arr.length <= 105
1 <= arr[i] <= 106