#P17882. Yet Another MST Problem

Yet Another MST Problem

对于一个非负整数集合 SS,定义 mex⁡(S)\operatorname{mex}(S) 为不属于 SS 的最小非负整数。

给定一个长度为 nn 的排列 pp,包含 0,1,…,n−10,1,\ldots,n-1 各一次,以及 mm 个闭区间 [li,ri][l_i,r_i]。

构造一张包含 mm 个顶点的无向完全图,第 ii 个顶点对应第 ii 个区间。对于每一对不同顶点 i,ji,j,它们之间的边权为这两个区间所包含的排列元素的并集的 MEX,即

$$w(i,j)=\operatorname{mex}\bigl(\{p_t\mid t\in[l_i,r_i]\cup[l_j,r_j]\}\bigr).$$

求这张图的最小生成树的总权值。

输入格式

第一行两个整数 n,mn,m。

第二行 nn 个整数 p1,p2,…,pnp_1,p_2,\ldots,p_n。

接下来 mm 行,第 ii 行两个整数 li,ril_i,r_i,表示第 ii 个区间。

输出格式

输出一个整数,表示最小生成树的总权值。

数据范围

  • 2≤n,m≤3×1052\le n,m\le3\times10^5。
  • pp 是 0,1,…,n−10,1,\ldots,n-1 的一个排列。
  • 1≤li≤ri≤n1\le l_i\le r_i\le n。
  • 不同编号的区间可以完全相同,仍对应不同顶点。

样例 1

6 4
3 1 5 2 0 4
3 6
1 2
2 5
4 6
8

样例 2

2 2
0 1
1 2
1 2
2