$n$ 個の正整数からなる配列 $a$ が与えられます。ただし、$a$ の一部の要素は欠損しており、代わりに $0$ に置き換えられています。
区間 $[\ell, r]$ における $a$ の振幅(oscillation)を $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$ と定義します。
$[\ell_i, r_i]$ の形をした $q$ 個の区間が与えられます。すべての $q$ 個の区間における $a$ の振幅の総和が最小になるように、$a$ に含まれる各 $0$ をそれぞれある正整数に置き換えてください。
入力
1 行目には 2 つの整数 $n$ と $q$($1 \le n, q \le 2 \cdot 10^5$)が与えられます。
2 行目には配列の要素を表す $n$ 個の整数 $a_1, \dots, a_n$($0 \le a_i \le 10^9$)が与えられます。ここで、$a_i = 0$ は $i$ 番目の要素が欠損していることを意味します。
続く $q$ 行には区間が記述されています。各行には 2 つの整数 $\ell_i$ と $r_i$($1 \le \ell_i \le r_i \le n$)が与えられます。
出力
与えられたすべての区間における $a$ の振幅の総和の最小値を表す 1 つの整数を出力してください。
入出力例
入力 1
5 2 2 1 0 3 2 1 3 3 5
出力 1
2
入力 2
5 3 1 0 3 0 1 1 2 2 4 5 5
出力 2
2
入力 3
7 4 4 4 0 1 0 3 4 1 3 1 3 3 5 4 7
出力 3
6
注記
1 番目の例では、唯一の最適な配列は $a = [2, 1, 2, 3, 2]$ です。
2 番目の例では、最適な配列が複数存在します。例えば、$a = [1, 2, 3, 2, 1]$ は最適です。
3 番目の例では、最適な配列が複数存在します。例えば、$a = [4, 4, 4, 1, 2, 3, 4]$ は最適です。