C - 难题

题目描述

有一个长度为 $n$ 的正整数序列 $a$ 。这个序列有一些位置的数值被涂改成了 $0$ ，你得到的是涂改后的序列 $a'$ 。

设 $p(a,l,r)=\max\limits_{i=l}^r a_{i}-\min\limits_{i=l}^r a_i$ 。

给定 $q$ 以及 $q$ 对整数 $(l_i,r_i)$ ，定义 $f(a)=\sum\limits_{i=1}^q p(a,l_i,r_i)$ 。

你需要计算：在所有可能的序列 $a$ 中，$f(a)$ 的最小值。

输入格式

第一行两个整数 $n,q$ 。

第二行 $n$ 个整数，表示序列 $a'$ 。若 $a'_i=0$ ，则 $a_i$ 可以是任一正整数，否则 $a_i=a'_i$ 。

第三行到第 $q+2$ 行，每行输入两个整数，其中第 $i$ 行代表 $l_{i-2},r_{i-2}$ 。

输出格式

输出一行一个整数，代表答案。

样例

样例 1 输入

7 4
514 514 0 1 0 114 514
1 3
1 3
3 5
4 7
4 7

样例 1 输出

1026

更多样例

见下发文件。

数据范围

所有数据满足：$n,q\le 2*10^5,0\le a'_i\le 10^9,1\le l_i\le r_i\le n$ 。

特殊性质 A ：$\forall 1\le i\le n,a_i\le 2$

特殊性质 B ：$\forall 1\le i\le n,a_i\le 5$