Problem H
Bridge building

In ancient days, long before even LTH existed, there were $M$ pairs of lovers living along the Söderåsen ridge. Each of the $2M$ people lived at some integer distance in meters from the start of the ridge, and unfortunately, not in the same place as their partner.

The shape of the ridge could be modeled as a list of positive integers $H$, the $i$th of which represents the height above sea level $i$ meters away from the start of the ridge. Walking one meter along the ridge would take the inhabitants as many minutes as the difference in height plus one (so moving from position $i$ to $i + 1$ would take $|H_ i - H_{i+1}| + 1$ minutes).

The people living along Söderåsen eventually grew tired of walking for days on end in order to meet their loved ones, and so decided to build one bridge connecting two positions along the ridge. A bridge could have been built between indices $i$ and $j$ if $j > i$, $H_ i = H_ j$ and $H_ k < H_ i$ for every integer $k$ strictly between $i$ and $j$. Such a bridge would allow people to walk from position $i$ to $j$ in $|j - i|$ minutes.

Unfortunately, the ancient Scanians did not have access to computers or courses in algorithm design, and so the bridge that was built may not have been the best one possible. The best bridge is one that makes the sum of the time it takes each pair to reach each other as small as possible. If the best possible bridge had been built, what would this sum have been?

Input

The first line of input contains two integers $N$ and $M$, where $2 \leq N \leq 200\, 000$ and $1 \leq M \leq 200\, 000$, the length of the ridge in meters and the number of pairs living along the ridge respectively.

The second line contains $N$ integers $H_1 \dots H_ N$, where $0 \leq H_ i \leq 10^6$, representing the height of the ridge.

Each of the next $M$ lines contain two integers $a_ i$ and $b_ i$, where $a_ i, b_ i \in \{ 1, \ldots , N \} , a_ i \neq b_ i$, the position along the ridge where the first and second person in pair $i$ lived.

It is guaranteed that there is at least one pair of positions between which a bridge can be built.

Output

Output a single integer, the smallest possible sum of distances between the pairs if an optimal bridge is built.

Scoring

Your solution will be tested on a set of test case groups. To get the points for a group, you need to pass all the test cases in the group.

Sample Description

In sample input 1, there is only one possible bridge, between the two positions with height $4$. Building this bridge reduces the distance between the two people from $10$ to $7$.

5 1
3 4 1 3 4
1 4

7

13 4
4 5 4 3 1 4 3 1 4 5 4 4 5
8 6
4 9
1 10
11 13

32