Девочка Аня выписала на доске $$$N$$$ различных чисел в порядке возрастания, а затем задумалась, что с ними можно сделать интересного? Проходящий мимо мальчик Боря заметил раздумья Ани и предложил ей сыграть в следующую игру: надо выписать на доску все упорядоченные тройки чисел $$$(a, b, c)$$$ такие, что квадратное уравнение $$$ax^2 + bx + c = 0$$$ ($$$a \neq 0$$$) имеет по крайней мере один вещественный корень. Две тройки $$$(a_1, b_1, c_1)$$$ и $$$(a_2, b_2, c_2)$$$ считаются различными, если $$$a_1 \neq a_2$$$ или $$$b_1 \neq b_2$$$ или $$$c_1 \neq c_2$$$. Одно и то же число можно использовать больше одного раза. Школьники выписали какое-то количество троек и решили проверить себя. Помогите им посчитать, сколько всего таких упорядоченных троек должно быть выписано на доске.
В первой строке записано натуральное число $$$N$$$ ($$$2 \le N \le 6000$$$) — количество чисел, записанных на доске.
Во второй строке записано $$$N$$$ целых чисел $$$a_i$$$ ($$$0 \le a_1 \lt a_2 \lt \dots \lt a_n \le 10^9$$$) — список чисел, записанных на доске.
В единственной строке выведите количество упорядоченных троек, которое нужно будет выписать на доске по модулю $$$274876858367$$$.
В задаче $$$4$$$ подзадачи. Подзадача $$$0$$$ — тесты из условия, за неё баллы не начисляются. Тестирование подзадачи начинается, если пройдены все тесты в необходимых подзадачах. Система оценки «полная» означает, что решению будут начисляться баллы только при успешном прохождении всех тестов данной подзадачи.
| Подзадача | Баллы | Дополнительные | Необходимые | Система |
| ограничения | подзадачи | оценки | ||
| $$$0$$$ | $$$0$$$ | Тесты из условия | — | — |
| $$$1$$$ | $$$21$$$ | $$$N \le 500$$$ | $$$0$$$ | полная |
| $$$2$$$ | $$$22$$$ | $$$N \le 1100$$$ | $$$0,\ 1$$$ | полная |
| $$$3$$$ | $$$31$$$ | $$$N \le 2000$$$ | $$$0,\ 1,\ 2$$$ | полная |
| $$$4$$$ | $$$26$$$ | $$$N \le 6000$$$ | $$$0,\ 1,\ 2,\ 3$$$ | полная |
51 2 3 4 5
24
