Дан массив a1, a2, ..., an. Рассмотрим мультимножество S, состоящее из всех попарных произведений элементов массива, то есть S = { ai aj для всех i < j }. Требуется найти k-й по возрастанию элемент в этом мультимножестве. В первой строке входных данных

Для решения этой задачи при больших ограничениях ($n \le 2 \cdot 10^5$) полный перебор всех пар (их количество достигает $\approx 2 \cdot 10^{10}$) невозможен. Мы воспользуемся бинарным поиском по ответу.

1. Дано

• Размер массива: $n$ ($1 \le n \le 2 \cdot 10^5$).
• Порядковый номер: $k$ ($1 \le k \le \frac{n(n-1)}{2}$).
• Массив элементов: $A = \{a_1, a_2, \dots, a_n\}$.
• Мультимножество $S = \{a_i \cdot a_j \mid 1 \le i < j \le n\}$.

2. Найти

• $k$-й по возрастанию элемент в $S$.

3. Решение

Шаг 1: Бинарный поиск Диапазон возможных значений произведений лежит от $min\_val = -10^{18}$...