Республиканская олимпиада по информатике 2022 года за 11 класс | Казахстанские олимпиады

Задача A. Покраска суммой

У вас есть массив целых чисел $a_1,...,a_n$ размера $n$. Изначально каждое число массива покрашено в белый цвет.

За одну операцию вы можете:

1. Выбрать три белых числа $(a_i, a_j, a_k) (1 \leq i,j,k, \leq n, i \neq j, j \neq k, i \neq k).$

2. Если значение $a_i + a_j$ строго больше $a_k$, покрасить $a_k$ в черный цвет.

Вы обязаны повторять эту операцию до тех пор, пока это возможно. В процессе некоторые числа будут перекрашены в черный цвет, а остальные — останутся белыми.

От вас требуется посчитать количество всевозможных конечных раскрасок.

Формат входного файла

В первой строке входного файла дано одно целое число $n$ — размер массива $(3 \leq n \leq 10^5)$.

Во второй строке даны $n$ целых чисел $a_1, . . . , a_n(−10^9 \leq a_i \leq 10^9)$.

Формат выходного файла

Выведите одно целое число — количество всевозможных конечных раскрасок. Можно показать,что в заданных ограничениях ответ никогда не превосходит $10^{18}$.

Система оценки

Примеры

Вход

3
2 2 5

Выход

2

Вход

4
-3 1 2 2

Выход

3