$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$개가 주어집니다. $a$에 있는 각 0을 양의 정수로 바꾸어, $q$개의 모든 구간에서 $a$의 진폭의 합을 최소화하세요.
입력
첫 번째 줄에는 두 정수 $n$과 $q$($1 \le n, q \le 2 \cdot 10^5$)가 주어집니다.
두 번째 줄에는 배열의 원소를 나타내는 $n$개의 정수 $a_1, \dots, a_n$($0 \le a_i \le 10^9$)이 주어집니다. 여기서 $a_i = 0$은 $i$번째 원소가 유실되었음을 의미합니다.
다음 $q$개의 줄에는 구간들이 설명됩니다. 각 줄에는 두 정수 $\ell_i$와 $r_i$($1 \le \ell_i \le r_i \le n$)가 주어집니다.
출력
주어진 모든 구간에서 $a$의 진폭의 합의 최솟값을 나타내는 정수 하나를 출력합니다.
예제
입력 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
참고
첫 번째 예제에서 유일한 최적 배열은 $a = [2, 1, 2, 3, 2]$입니다.
두 번째 예제에서는 최적 배열이 여러 개 존재합니다. 예를 들어 $a = [1, 2, 3, 2, 1]$이 최적입니다.
세 번째 예제에서는 최적 배열이 여러 개 존재합니다. 예를 들어 $a = [4, 4, 4, 1, 2, 3, 4]$가 최적입니다.