子元排序

Background

杭四严查晚自习，书记亲自抓。然而大家只是给书记做做样子，谁都知道想要真正达到理想中的晚自习是不可能的。具体来讲，每个同学都有一个编号，你需要保证受检查区段内的同学编号是升序的，才能让该区段晚自习安静下来。然而给同学换位子是占用时间的。请你给出占用时间最少的换位子方法。

Description

给定同学的数量 $N$ ，编号从 $0$ 到 $N-1$。每个同学只能与其相邻的同学换位子以移动，每次调换占用时间为 $1$ 。同时，子元将会按顺序抽查任意 $M$ 个 $a_i$ 到 $b_i$ 区段内的学生是否安静。你可以在每次抽查前调换位置，但调换后的位置信息会保留，也就是意味着下一次调换是在这一次基础上进行的调换（当然如果你愿意，你也可以一次性调换好，不过是不是最短时间就不得而知了）。最后输出总调换耗时 $T$ 。

Input Format

第一行包含两个正整数 $N,M$，表示了同学的数目与抽查的次数。

第二行包含 $N$ 个非负乱序整数 $0$ 到 $N-1$，表示了每个同学初始的座位顺序。

接下来 $M$ 行，每行 $2$ 个非负整数 $a,b$，表示了受检查区段为 $a$ 到 $b$ 。

Output

一个整数 $T$ ，表示总调换耗时。

Sample

Input 1

5 4
2 3 0 4 1
3 4
2 3
1 3
0 1

Output 1

4

Explanation

显然，当检查34区段时，学生为 $4$ 和 $1$ ，则需将其调换顺序；检查23区段时，$0$ 和 $1$ 已经升序；检查13区段时，学生为 $3, 0, 1$ ，则需要将 $3$ 向后移两格；检查01区段时，因为移动后该区段学生变为了 $2, 0$ ，则还需要调换一次。 故答案为 $4$ 。