Вам дан массив \(a_1, a_2, \dots, a_n\) из \(n\) различных целых чисел. Вы можете выполнять следующую операцию:
Обратите внимание, что после каждой операции массив меняется, и последующие операции выполняются с новым массивом.
Какое максимальное число раз вы можете выполнить операцию?
Первая строка содержит одно целое число \(n\) (\(2 \le n \le 10^6\)).
Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq 10^6\)). Все \(a_i\) различны.
Выведите одно целое число — максимальное количество операций, которое можно выполнить с данным массивом.
В первом примере один из способов выполнить максимальное число операций такой:
Можно показать, что не существует способа выполнить больше \(3\) операций с массивом.
Во втором примере можно добавить \(3\), затем \(1\), затем \(5\) и \(2\).
5 4 20 1 25 30
3
3 6 10 15
4
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач