You are given an array $a$ consisting of $n$ positive integers. However, some elements of $a$ are missing, and they are replaced by zeroes.
Define the oscillation of $a$ on a segment $[\ell, r]$ to be $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.
You are given $q$ segments in the form $[\ell_i, r_i]$. Replace each zero in $a$ with a positive integer to minimize the sum of oscillations of $a$ on all $q$ segments.
Input
The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$).
The second line contains $n$ integers $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$): the elements of the array. Here, $a_i = 0$ means that the $i$-th element is missing.
The next $q$ lines describe the segments. Each of them contains two integers $\ell_i$ and $r_i$ ($1 \le \ell_i \le r_i \le n$).
Output
Print a single integer: the minimum sum of oscillations of $a$ on all the given segments.
Examples
Input 1
5 2 2 1 0 3 2 1 3 3 5
Output 1
2
Input 2
5 3 1 0 3 0 1 1 2 2 4 5 5
Output 2
2
Input 3
7 4 4 4 0 1 0 3 4 1 3 1 3 3 5 4 7
Output 3
6
Note
In the first example, the only optimal array is $a = [2, 1, 2, 3, 2]$.
In the second example, there are several optimal arrays. For example, $a = [1, 2, 3, 2, 1]$ is optimal.
In the third example, there are several optimal arrays. For example, $a = [4, 4, 4, 1, 2, 3, 4]$ is optimal.