Задача с ШАДа

Дается массив положительных целых чисел a длины n <= 1e5.
Набор чисел называется хорошим, если любое число из набора не больше суммы двух других чисел из набора. Найдите хороший набор из массива с максимальной суммой.
Например
5
3 2 5 4 1
Возьмем числа 3, 2, 5, 4

5
1 2 4 8 16
Возьмем числа 8, 16

Решение:
Отсортируем массив a и будем искать ответ в отсортированном массиве.
Пусть мы взяли числа на позициях i1, i2, ..., ik. Чтобы набор был хорошим нам необходимо и достаточно, чтобы выполнялось неравенство a[i1] + a[i2] >= a[ik].

Что вы можете сказать про i1, i2 в оптимальном ответе ?

Утверждение i1 + 1 = i2 - это правда так как иначе вы могли передвинуть i1 к позиции i2 - 1 сохраняя неравенство a[i1] + a[i2] >= a[ik], но уже с большей суммой.
Из этого утверждение получаем вывод:
i1 + 1 = i2
i2 + 1 = i3
i3 + 1 = i4
......
То бишь индексы - это непрерывный отрезок.
Зная эти факты вы наверное уже поняли, что задачу будем решать двумя указателями. Для этого достаточно для каждого l находить максимальный r для которого выполнено неравенство a[l] + a[l + 1] >= a[r].

Время работы: O(n * logn)