Сізге $n$ оң бүтін саннан тұратын $a$ массиві берілген. Алайда $a$ массивінің кейбір элементтері түсіп қалған және олар нөлдермен алмастырылған.
$a$ массивінің $[\ell, r]$ кесіндісіндегі тербелісі деп $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$ мәнін атайық.
Сізге $[\ell_i, r_i]$ түріндегі $q$ кесінді берілген. Барлық $q$ кесіндідегі $a$ массивінің тербелістерінің қосындысын барынша азайту үшін $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]$ тиімді болып табылады.