P15018 [UOI 2020 II Stage] 日历

哥萨克胡子来到了一个奇妙的世界。他发现，这个世界将恰好存在 $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$ 个月份的天数。

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

第一个样例的解释： 考虑所有三元组： $(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 完成