נתון לכם מערך $a$ המורכב מ-$n$ מספרים שלמים חיוביים. עם זאת, חלק מהאיברים של $a$ חסרים, והם הוחלפו באפסים.
נגדיר את התנודה (oscillation) של $a$ על מקטע $[\ell, r]$ בתור $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.
נתונים לכם $q$ מקטעים מהצורה $[\ell_i, r_i]$. החליפו כל אפס ב-$a$ במספר שלם חיובי כך שסכום התנודות של $a$ על כל $q$ המקטעים יהיה מינימלי.
קלט
השורה הראשונה מכילה שני מספרים שלמים $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]$ הוא אופטימלי.