← 返回题目列表

Codeforces · 961/E

E. 图富拉玛

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

有一天,Polycarp 决定重新观看他最喜欢的著名电视剧“Tufurama”的一集。当他通过搜索“观看 Tufurama 第 3 季第 7 集在线完整高清免费”只得到第 7 季第 3 集的结果时,他感到非常惊讶。这让波利卡普感到困惑——如果他决定有一天重新观看整个系列却找不到合适的剧集怎么办?波利卡普现在想要计算他被迫使用某种不同方法搜索剧集的次数。

电视剧有 n 季(编号为 1 到 n),第 i 季有 ai 集(编号为 1 到 ai)。 Polycarp 认为,如果对于某对整数 x 和 y (x < y),同时存在第 x 季第 y 集和第 y 季第 x 集,那么这些搜索查询之一将包含错误的结果。帮助波利卡普计算出这样的对的数量!

输入

第一行包含一个整数 n (1 ≤ n ≤ 2·105) — 季节数。

第二行包含 n 个整数,以空格分隔 a1, a2, ..., an (1 ≤ ai ≤ 109) — 每季的剧集数。

输出

打印一个整数 — x 和 y 对的数量 (x < y),使得同时存在第 x 季第 y 集和第 y 季第 x 集。

示例

输入 #1

5
1 2 3 4 5

输出 #1

0

输入 #2

3
8 12 7

输出 #2

3

输入 #3

3
3 2 1

输出 #3

2

注意

第二个示例中可能的对:

1. x = 1,y = 2(第 1 季第 2 集 $$\text{图像中未提供用于生成文本的公式。}$$ 第 2 季第 1 集);
2. x = 2,y = 3(第 2 季第 3 集 $$\text{图像中未提供用于生成文本的公式。}$$ 第 3 季第 2 集);
3. x = 1,y = 3(第 1 季第 3 集 $$\text{图像中未提供用于生成文本的公式。}$$ 第 3 季第 1 集)。

在第三个示例中:

1. x = 1,y = 2(第 1 季第 2 集 $$\text{图像中未提供用于生成文本的公式。}$$ 第 2 季第 1 集);
2. x = 1,y = 3(第 1 季第 3 集 $$\text{图像中未提供用于生成文本的公式。}$$ 第 3 季第 1 集)。