围棋是我国古代的智慧结晶。
最近经常上网的小L迷上了看一位围棋八冠王选手的直播，为了去了解他的更多，小L便想要去学习围棋，希望有朝一日能与他博弈。但是奈何小L的围棋天赋不高，但是在学习围棋的过程中，他想到了一个类似于围棋的新游戏：
棋盘大小为 $$$n*n$$$ ，左上角坐标为 $$$(1,1)$$$ ，从上到下 $$$x$$$ 坐标递增，从左至右 $$$y$$$ 坐标递增，两位玩家在棋盘右上半部分(即 $$$x \le y$$$ 的部分)轮流落黑白色的棋子（先落黑子再落白子），一颗棋子的左下能落子的区域(包括该行该列)称为该棋子的"控制区"，保证棋盘上所有的棋子的"控制区"只会真包含或者不交。
一颗棋子的"气"定义为它"控制区"内权值不小于它的同色棋子"气"的最大值+1，如果"控制区"内除自己以外没有同色棋子则该点"气"为1，若某区域内没有 $$$x$$$ 色棋子，则该区域内 $$$x$$$ 色棋子的"气"的最大值视为0。
同时，小L有一个序列 $$$a$$$ ，并定义格点 $$$M(x,y)$$$ 的权值为 $$$\min\limits_{x \le i \le y}(a_i)$$$ 。
整局棋下完后分别算双方的积分，积分规则如下：
I.一颗棋子的"控制区"内与该颗棋子颜色相同（包括该颗棋子）的所有棋子所在的格点中，相同权值出现的最大次数如果大于"控制区"内另一种颜色的棋子所在格点的相同权值出现的最大次数，则称该方玩家获得一分。
II.一颗棋子的"气"若大于其"控制区"中所有异色棋子的"气"，则该方玩家获得一分。
现在给定序列 $$$a$$$ 和一次游戏两人轮流落子的坐标，求两人最后的分数分别为多少。
第一行输入两个正整数 $$$n,m$$$ ($$$1 \le n,m \le 2 \times 10^5$$$) ，代表序列 $$$a$$$ 的长度和双方所下棋子的个数。
第二行输入 $$$n$$$ 个数，代表序列 $$$a$$$ ($$$0 \le a_i \le 10^9$$$) 的值。
接下来 $$$m$$$ 行每行输入两个数 $$$x,y$$$ ($$$1 \le x \le y \le n$$$) ，代表每个棋子的横纵坐标。
数据保证棋盘上所有的棋子的"控制区"只会真包含或者不交。
一行两个整数，代表黑棋方的分数和白棋方的分数，中间用一个空格隔开。
5 41 2 3 4 11 51 31 14 5
3 2
13 91 3 5 6 4 2 9 21 10 6 21 1 31 1311 125 86 71 91 43 41 210 13
3 8
样例一示意图 在样例1中，四个有棋子的格点的权值均为1, $$$[1,1],[1,3],[4,5]$$$ 的控制区内均无同色棋子，则它们的气均为1, $$$[1,5]$$$ 控制区内有 $$$[1,1]$$$ 这颗同色棋子，则 $$$[1,5]$$$ 的气为2。
对于规则I：
$$$[1,5]$$$ 控制区内黑子出现次数最多的数字为1，为2次，白子出现次数最多的数字为1，为2次，不计分；
$$$[1,3]$$$ 控制区内白子出现次数最多的数字为1，为1次，黑子出现次数最多的数字为1，为1次，不计分；
$$$[1,1]$$$ 控制区内黑子出现次数最多的数字为1，为1次，没有白子出现，黑子方计一分；
$$$[4,5]$$$ 控制区内白子出现次数最多的数字为1，为1次，没有黑子出现，白子方计一分；
对于规则II：
$$$[1,5]$$$ 控制区内白子最大的气为1，而其本身的气为2，黑子方计一分；
$$$[1,3]$$$ 控制区内黑子最大的气为1，而其本身的气为1，不计分；
$$$[1,1]$$$ 控制区内白子最大的气为0，而其本身的气为1，黑子方计一分；
$$$[4,5]$$$ 控制区内黑子最大的气为0，而其本身的气为1，白子方计一分；
综上所述，黑子得分为3，白子得分为2。
