تُعطى لك مصفوفة $a$ تتكون من $n$ من الأعداد الصحيحة الموجبة. ومع ذلك، فإن بعض عناصر $a$ مفقودة، وقد تم استبدالها بأصفار.
عرّف تذبذب المصفوفة $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]$ مثلى.