Козак Вус і календар#114

Козак Вус і календар

0.5 seconds

256 megabytes

Hard

Козак Вус потрапив у дивовижний світ. Як він з'ясував, цей світ існуватиме рівно $n$ календарних років. Причому кожен рік складається з $n$ місяців, а місяць під номером $i$ триває рівно $a_{i}$ a_i діб.

Козак одразу зрозумів, що в цьому світі використовують один із наступних шести форматів календарних дат: Д.М.Р, Д.Р.М, М.Д.Р, М.Р.Д, Р.М.Д та Р.Д.М (замість букви Р пишуть номер року, замість М "— номер місяця, а замість Д "— день місяця). Вуса зацікавила кількість впорядкованих трійок ( $1 \leq x, y, z \leq n$ 1 \leq x,y,z \leq n) таких, що для будь-якого формату, календарна дата x.y.z є коректною (ця дата описує реально існуючу добу).

Наприклад, при $n = 3$ n = 3, $a_{1} = 2$ a_1 = 2, $a_{2} = 3$ a_2 = 3 і $a_{3} = 1$ a_3 = 1, дата 2.3.1 не є коректною для формату Д.М.Р (дата описує другий день третього місяця, хоча третій місяць триває одну добу). У свою чергу, дата 1.1.1 є коректною для всіх форматів.

Input

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 5 \cdot 1 0^{3}$ 1 \leq n \leq 5 \cdot 10^3) "— кількість місяців у календарному році, яка одночасно є і кількістю календарних років.

Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, ..., a_{n}$ a_1,a_2,...,a_n ( $1 \leq a_{i} \leq n$ 1 \leq a_i \leq n) "— кількість діб в $i$ -му місяці.

Output

Виведіть одне число "— кількість трійок.

Examples

Example 1

Example 2

Note

Пояснення до першого прикладу:

Розглянемо всі трійки:

$(1, 1, 1)$ (1, 1, 1) "— підходить під всі формати.

$(1, 1, 2)$ (1, 1, 2) "— підходить під всі формати.

$(1, 2, 1)$ (1, 2, 1) "— підходить під всі формати.

$(1, 2, 2)$ (1, 2, 2) "— не підходить під формати Р.Д.М та Р.М.Д.

$(2, 1, 1)$ (2, 1, 1) "— підходить під всі формати.

$(2, 1, 2)$ (2, 1, 2) "— не підходить під формати Д.Р.М та М.Р.Д.

$(2, 2, 1)$ (2, 2, 1) "— не підходить під формати М.Д.Р та Д.М.Р.

$(2, 2, 2)$ (2, 2, 2) "— не підходить під формати Д.Р.М, М.Д.Р, М.Р.Д, Р.Д.М, Р.М.Д та Д.М.Р.

Трійки $(1, 1, 3)$ (1, 1, 3), $(1, 2, 3)$ (1, 2, 3), $(1, 3, 1)$ (1, 3, 1), $(1, 3, 2)$ (1, 3, 2), $(1, 3, 3)$ (1, 3, 3), $(2, 1, 3)$ (2, 1, 3), $(2, 2, 3)$ (2, 2, 3), $(2, 3, 1)$ (2, 3, 1), $(2, 3, 2)$ (2, 3, 2), $(2, 3, 3)$ (2, 3, 3), $(3, 1, 1)$ (3, 1, 1), $(3, 1, 2)$ (3, 1, 2), $(3, 1, 3)$ (3, 1, 3), $(3, 2, 1)$ (3, 2, 1), $(3, 2, 2)$ (3, 2, 2), $(3, 2, 3)$ (3, 2, 3), $(3, 3, 1)$ (3, 3, 1), $(3, 3, 2)$ (3, 3, 2) та $(3, 3, 3)$ (3, 3, 3) не підходять, бо кількість днів в кожному місяці менша за $3$ (серед форматів Д.Р.М, Р.Д.М та Р.М.Д буде хоча б один, під який трійка не буде підходити).