#P17896. Absolutely Flat

Absolutely Flat

题目描述

有一个长度为 nn 的正整数数组,其中一些元素缺失。在输入中,缺失的元素用 00 表示。

对于区间 [l,r][l,r],定义它的波动值为区间内最大值与最小值之差:

$$\max(a_l,a_{l+1},\ldots,a_r)-\min(a_l,a_{l+1},\ldots,a_r).$$

给定 qq 个区间 [li,ri][l_i,r_i]。请将每个缺失元素替换成一个正整数,使这 qq 个区间的波动值之和最小。求这个最小值。

同一个缺失位置只能填一个值,填入的值会同时用于所有包含该位置的区间。已经给出的非零元素不能修改。区间可以重复,重复给出的区间需要重复计入总和。

输入格式

第一行包含两个整数 n,qn,q。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,其中 ai=0a_i=0 表示该元素缺失。

接下来 qq 行,每行包含两个整数 li,ril_i,r_i,表示一个区间。

输出格式

输出一个整数,表示所有给定区间波动值之和的最小值。

数据范围

  • 1≤n,q≤2000001\le n,q\le200000;
  • 0≤ai≤1090\le a_i\le10^9;
  • 1≤li≤ri≤n1\le l_i\le r_i\le n。

样例输入

3 2
1 0 3
1 2
2 3

样例输出

2

样例解释

将缺失元素填为 22,两个区间的波动值都是 11,总和为 22。填为 11 或 33 也能得到最优答案。