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

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

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

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

Input

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

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

Output

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

Examples

Note

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

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

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