17. Кодмастер

Анонимный программист под псевдонимом Кодмастер уже не первый год поражает IT-индустрию своими инновационными проектами с открытым исходным кодом. Эксперты по разработке программного обеспечения пытаются разгадать секрет популярности Кодмастера. Чтобы приблизиться к ответу, к задаче привлекли вас. Кодмастер создаёт программы, использующие различные алгоритмы, и каждый алгоритм имеет свою сложность. Эксперты считают, что алгоритмы с линейной сложностью ($O(n)$) создают особую эффективность в программах Кодмастера. Вам нужно определить при помощи «индекса линейной сложности», насколько часто алгоритмы с линейной сложностью встречаются в проектах программиста.

Ваша задача: на основе набора $a_1,a_2,a_3,...,a_n$ (число алгоритмов с линейной сложностью в $n$ проектах Кодмастера) рассчитать «индекс линейной сложности», то есть такое максимальное число проектов k, что в каждом из них как минимум $k^2$ алгоритмов с линейной сложностью. Помогите сделать это максимально быстро.

Например: пусть в $5$ проектах $1,0,4,5,100$ алгоритмов с линейной сложностью. Тогда индекс равен $2$, так как есть хотя бы $2$ значения $a_i$, которые больше, чем $2^2$ $(4,5,100\geq2^2)$, при этом индекс меньше 3, так как только 1 значение $a_{i}$ больше $3^2$ $(100\geq3^2)$.

Формат ввода

В первой строке вводится число $n$ $(1\leq n\leq 10^7)$.

Во второй строке вводится набор целых чисел $a_{i}$ $(0 \leq a_{i} \leq 10^5)$ через пробел.

Формат вывода

Необходимо вывести число $k$ — «индекс линейной сложности».