Задача Vus. Козак Вус потрапив у дивовижний світ. Як вiн з’ясував, цей світ існуватиме рівно n календарних років. Причому кожен рік складається з n місяців, а місяць пiд номером i триває рiвно ai дiб. Козак одразу зрозумiв, що в цьому свiтi використовують один iз наступних шести форматiв календарних дат: Д.М.Р, Д.Р.М, М.Д.Р, М.Р.Д, Р.М.Д та Р.Д.М (замiсть букви Р пишуть номер року, замiсть М—номер мiсяця, а замiсть Д—день мiсяця).
Вуса зацiкавила кiлькiсть впорядкованих тройок (1 ≤x,y,z ≤ n) таких, що для будь-якого формату, календарна дата x.y.z є коректною (ця дата описує реально існуючу добу). Наприклад, при n = 3, a1 = 2, a2 = 3 i a3 = 1, дата 2.3.1 є коректною для формату Р.М.Д, але не є коректною для формату Д.М.Р (третiй мiсяць триває всього одну добу). У свою чергу, дата 1.1.1 є коректною для всiх форматiв.
Технічні умови. Програма Vus читає з пристрою стандартного введення цiле число n (1 ≤ n ≤ 5·103)—кiлькiсть мiсяцiв у календарному роцi, далі в тому ж рядку через пропуски n цiлих чисел a1,a2,...,an (1≤ai ≤ n)—кiлькiсть дiб в i-му мiсяцi. Програма виводить на пристрій стандартного виведення одне число—кiлькiсть трiйок.
Приклади
|
Введення |
Виведення |
Пояснення до першого прикладу |
|
3 2 1 2 5 4 3 4 2 1 |
4 30 |
Розглянемо всi трiйки: (1, 1, 1)—підходить під всi формати (1, 1, 2)—підходить пiд всi формати (1, 2, 1)—пiдходить пiд всi формати (1, 2, 2)—не пiдходить пiд формати Р.Д.М та Р.М.Д (2, 1, 1)—пiдходить пiд всi формати (2, 1, 2)—не пiдходить пiд формати Д.Р.М та М.Р.Д (2, 2, 1)—не пiдходить пiд формати М.Д.Р та Д.М.Р (2, 2, 2)—не пiдходить пiд формати Д.Р.М, М.Д.Р, М.Р.Д, Р.Д.М, Р.М.Д та Д.М.Р Трiйки (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) не пiдходять, бо кiлькiсть днiв в кожному мiсяцi менша за 3 (серед форматів Д.Р.М, Р.Д.М та Р.М.Д буде хоча б один, пiд який трiйка не буде пiдходити).
|