爱丽丝正在和她的好朋友玛丽莎玩游戏。
有$$$n$$$个盒子排成一行,从左到右用从$$$1$$$到$$$n$$$的整数编号。玛丽莎会将一个洋娃娃藏在其中一个盒子里。那么爱丽丝将有 $$$m$$$ 机会猜出洋娃娃在哪里。如果爱丽丝正确猜出了盒子的数量,即洋娃娃现在所在的位置,她将赢得游戏,否则,她的朋友将赢得游戏。
为了获胜,魔理沙会使用一些不公平的伎俩。每次爱丽丝猜到一个盒子后,她就可以将娃娃移动到相邻的盒子或将其保留在原处。对于所有 $$$1 \leq i \leq n - 1$$$,框 $$$i$$$ 和 $$$i + 1$$$ 都是相邻的。她也可以在比赛开始前使用一次这个技巧。
因此,游戏按以下顺序发生:游戏开始,Marisa 出戏,Alice 进行第一次猜测,Marisa 出戏,Alice 进行第二次猜测,Marisa 出戏,$$$\ldots$$$,Alice 进行第 $$$m$$$ 次猜测,Marisa 出戏,游戏结束。
Alice 提出了一个序列 $$$a_1, a_2, \ldots, a_m$$$。在第 $$$i$$$ 次猜测中,她会询问娃娃是否在 $$$a_i$$$ 盒子里。她想知道场景的数量 $$$(x, y)$$$ (对于所有 $$$1 \leq x, y \leq n$$$),这样,如果 Marisa 在游戏开始时将娃娃放在第 $$$x$$$ 个盒子上,并且在游戏结束时,娃娃将放在第 $$$y$$$ 个盒子里,那么 Marisa 就可以赢得游戏。帮助她计算这个数字。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$,用空格分隔 ($$$1 \leq n, m \leq 10^5$$$) - 盒子的数量和爱丽丝将进行的猜测的数量。
下一行包含 $$$m$$$ 整数 $$$a_1, a_2, \ldots, a_m$$$,以空格分隔 ($$$1 \leq a_i \leq n$$$),数字 $$$a_i$$$ 表示 Alice 在第 $$$i$$$ 次猜测中将猜测的盒子的编号。
输出
打印单行中的场景数量,或者盒子对的数量 $$$(x, y)$$$ ($$$1 \leq x, y \leq n$$$),这样如果 Marisa 将娃娃放入编号为 $$$x$$$ 的盒子里,她就可以用这样的方式进行欺骗,在游戏结束时娃娃将位于编号为 $$$y$$$ 的盒子里她会赢得比赛。
示例
输入 #1
3 3 2 2 2
输出 #1
7
输入 #2
5 2 3 1
输出 #2
21
注意
在第一个示例中,可能的情况为 $$$(1, 1)$$$、$$$(1, 2)$$$、$$$(2, 1)$$$、$$$(2, 2)$$$、$$$(2, 3)$$$、$$$(3, 2)$$$、$$$(3, 3)$$$。
我们以 $$$(2, 2)$$$ 为例。游戏期间玩偶所在的盒子可以是 $$$2 \to 3 \to 3 \to 3 \to 2$$$