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

Обмеження на час виконання 0,5 секунди

Обмеження на використання пам'яті 256 мегабайтів

Козак Вус потрапив у дивовижний світ. Як він з'ясував, цей світ існуватиме рівно $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 1 0^{3}$ ) "— кількість місяців у календарному році, яка одночасно є і кількістю календарних років.

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

Вихідні дані

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

Приклади

Вхідні дані #1

Відповідь #1

Вхідні дані #2

Відповідь #2

Примітка

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

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

$(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$ (серед форматів Д.Р.М, Р.Д.М та Р.М.Д буде хоча б один, під який трійка не буде підходити).