Take care of your garden

You have a large garden with many plants. Each of those plants requires to be watered. You have been away for the weekend, so you’d like to water all the plants as quickly as possible. But as it takes time, you’ve decided to water plants that have low humidity first.
Β 
notion image
Everything in the garden is planted in a long row, so moving from one plant to its neighbor takes 1 minute, and watering one plant also takes 1 minute.
Knowing the humidity levels for each of the plants, you’re wondering how many minutes it would take to water all the plants. You’re initially near the first plant.

Input

The first line of the input contains a single integer n (1 ≀ n ≀ ).
The next line contains n space-separated integers (1 ≀ ≀ n) the humidity levels for each plant.

Output

The program should print the number of minutes it would take you to water all the plants.

Examples

Input
Output
6 3 2 5 6 2 5
21

Explanation

  1. Go from the 1st plant to the 2nd β‡’ 1 minute
  1. Water the 2nd plant β‡’ 1 minute β‡’ 3 2 5 6 2 5
  1. Go from the 2nd plant to the 5th β‡’ 3 minutes
  1. Water the 5th plant β‡’ 1 minute β‡’ 3 2 5 6 2 5
  1. Go from the 5th plant to the 1st β‡’ 4 minutes
  1. Water the 1st plant β‡’ 1 minute β‡’ 3 2 5 6 2 5
  1. Go from the 1st plant to the 3rd β‡’ 2 minutes
  1. Water the 3rd plant β‡’ 1 minute β‡’ 3 2 5 6 2 5
  1. Go from the 3rd plant to the 6th β‡’ 3 minutes
  1. Water the 6th plant β‡’ 1 minute β‡’ 3 2 5 6 2 5
  1. Go from the 6th plant to the 4th β‡’ 2 minutes
  1. Water the 4th plant β‡’ 1 minute β‡’ 3 2 5 6 2 5
In total β†’ 1 + 1 + 3 + 1 + 4 + 1 + 2 + 1 + 3 + 1 + 2 + 1 = 21
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue