Director Cheeseburger has encountered a systemic risk to AUCPL Inc's future - a critical department is filled with chuds who do no work and play table tennis all day.

Cheeseburger is left with no choice but to lay off this entire department, but he must lay them off one-by-one due to system limitations. Additionally, each laid off employee will generate internet outrage by posting on Reddit and Hacker News based on the number of already-vacated desks contiguously to their left and right.

Cheeseburger is set on firing the employees in order of least productive to most productive. Calculate the total media outrage that will be generated so he can pay off his friendly Reddit executives to remove the posts.

Specifically, there are ~n~ employees sitting in a single row, indexed from ~1~ to ~n~. Each employee has a unique productivity score from ~1~ to ~n~, and employees are fired in increasing order of productivity. When each employee is laid off, they will generate an integer media outrage number equal to the number of already-laid-off colleagues' seats connected to them.

Equivalently, if ~L~ and ~R~ are the nearest still employed colleagues to the left and right of them (using ~1-n~ indexing, and ~0~ or ~n+1~ if there are none), the media outrage generated is ~R-L-2~.

Report the total sum of these outrage scores for all ~n~ layoffs, or maybe Director Cheeseburger will lay off your department next!

Input

The first line contains a single integer ~n~ ~(1 \leq n \leq 2 \times 10^5)~, the number of workers in the department to be laid off.

The next line contains a space-separated permutation of length ~n~. Specifically, it contains ~n~ space-separated integers ~a_i~ ~(1 \leq a_i \leq n)~, such that each integer ~1,\dots, n~ appears exactly once. This represents the productivity scores of each employee.

Output

Output the total media outrage generated as the sum of the scores defined above when laying off all ~n~ department employees in increasing order of their productivity scores.

Example

Input 1

3
3 2 1

Output 1

3

Initially, when position ~3~ is fired, no one has been laid off next to them so there is no outrage generated. Next, position ~2~ is next to the already-fired position ~3~, so an outrage of ~1~ is generated. Finally, position ~1~ is fired, and they are next to both of the already-fired colleagues, so a score of ~2~ is added, resulting in the final ~0+1+2=3~ outrage value.

Input 2

4
2 4 1 3

Output 2

4

The first two layoffs result in ~0~ outrage. The third results in ~1~, as only the colleague to position ~4~'s left has been laid off at this point. Finally all ~3~ other employees have been laid off when the final employee is laid off. So ~0+1+3=4~ is the total score.

Input 3

5
1 3 2 5 4

Output 3

6

We ran out of budget to make this worked solution, apologies. We hope this image will placate you instead.

Input 4

7
1 7 3 5 2 4 6

Output 4

14