题目描述

哥萨克胡子来到了一个奇妙的世界。他发现，这个世界将恰好存在 $n$ 个日历年。而且，每年由 $n$ 个月组成，编号为 $i$ 的月份恰好持续 $a_i$ 天。

哥萨克立刻明白，这个世界使用以下六种日历日期格式之一：日.月.年、日.年.月、月.日.年、月.年.日、年.月.日 和 年.日.月（其中 年 表示年份编号，月 表示月份编号，日 表示月份中的日期）。胡子感兴趣的是，有多少个有序三元组 ($1 \leq x, y, z \leq n$) 满足：对于 任何 一种格式，日历日期 x.y.z 都是有效的（即该日期描述了一个真实存在的日期）。

例如，当 $n = 3$、$a_1 = 2$、$a_2 = 3$、$a_3 = 1$ 时，日期 2.3.1 对于格式 日.月.年 是无效的（该日期描述的是第三个月的第二天，但第三个月只持续一天）。另一方面，日期 1.1.1 对于所有格式都是有效的。

输入格式

第一行包含一个整数 $n$ ($1 \leq n \leq 5 \cdot 10^3$) —— 日历年的月份数，同时也等于日历年数。

第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($1 \leq a_i \leq n$) —— 第 $i$ 个月份的天数。

输出格式

输出一个数字 —— 满足条件的三元组数量。

3
2 1 2

4

5
4 3 4 2 1

30

提示

第一个样例的解释：

考虑所有三元组：

$(1, 1, 1)$ —— 符合所有格式。

$(1, 1, 2)$ —— 符合所有格式。

$(1, 2, 1)$ —— 符合所有格式。

$(1, 2, 2)$ —— 不符合格式 年.日.月 和 年.月.日。

$(2, 1, 1)$ —— 符合所有格式。

$(2, 1, 2)$ —— 不符合格式 日.年.月 和 月.年.日。

$(2, 2, 1)$ —— 不符合格式 月.日.年 和 日.月.年。

$(2, 2, 2)$ —— 不符合格式 日.年.月、月.日.年、月.年.日、年.日.月、年.月.日 和 日.月.年。

三元组 $(1, 1, 3)$、$(1, 2, 3)$、$(1, 3, 1)$、$(1, 3, 2)$、$(1, 3, 3)$、$(2, 1, 3)$、$(2, 2, 3)$、$(2, 3, 1)$、$(2, 3, 2)$、$(2, 3, 3)$、$(3, 1, 1)$、$(3, 1, 2)$、$(3, 1, 3)$、$(3, 2, 1)$、$(3, 2, 2)$、$(3, 2, 3)$、$(3, 3, 1)$、$(3, 3, 2)$ 和 $(3, 3, 3)$ 不符合，因为每个月的天数都小于 $3$（在格式 日.年.月、年.日.月 和 年.月.日 中，至少有一个格式会使该三元组无效）。

翻译由 DeepSeek V3 完成