分数: 466 分
问题陈述
高桥是一家图书馆的图书管理员。图书馆有 N 架子排列成一排,编号 1, 2, \ldots, N 从左到右。
有一天,他执行归来的任务 M 书籍上架。还书的顺序是固定的:他按顺序一本一本地还—— 1st 书, 2第二本书, \ldots, M第本书。到的货架编号 i-th (1 \leq i \leq M) 书应归还的是 G_i。请注意,多本书可能会被归还到同一个书架上。
每次高桥返回 i-th (1 \leq i \leq M) 书到书架上,他记录了一个值 L_i 定义如下:
- L_i:其中 M - i 预定归还的书籍 (i+1)-th, (i+2)-th, \ldots, M第本书(即当前尚未上架的所有书籍) i第本书被返回),目标书架号为的图书数量 小于 G_i。当 i = M,有 0 这样的书,所以 L_M = 0.
当天的工作完成后,高桥必须写下记录值的总计 L_1 + L_2 + \cdots + L_M 在他的报告中。
给定货架数量 N, 图书数量 M,以及目的地货架编号 G_i 对于每本书,找到以下值 L_1 + L_2 + \cdots + L_M.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq G_i \leq N (1 \leq i \leq M)
- 所有输入值均为整数
输入
N M G_1 G_2 \vdots G_M
- 第一行包含一个整数 N 代表货架数量和一个整数 M 代表书籍数量,以空格分隔。
- 的 i-th (1 \leq i \leq M) 以下内容 M 行包含 G_i,目标货架编号 i第本书要归还。
输出
输出值 L_1 + L_2 + \cdots + L_M 在一行上。
示例输入 1
5 4 3 1 4 2
示例输出 1
3
示例输入 2
3 5 2 3 1 2 1
示例输出 2
6
示例输入 3
10 8 5 3 8 1 7 2 6 4
示例输出 3
15
示例输入 4
100 12 10 9 8 7 6 5 4 3 2 1 1 1
示例输出 4
63
示例输入 5
1 1 1
示例输出 5
0