← 返回题目列表

AtCoder · awc0051_e

E. 整理书籍

中文机器翻译题面 查看原题

分数: 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