Вася — большой любитель рыб, и родители подарили ему на Новый Год аквариум. Вася не имеет ученой степени по ихтиологии, поэтому считает, что заполнить новый аквариум муренами — неплохая идея. К сожалению, мурены — хищные рыбы, поэтому Вася решил выяснить, насколько опасна эта затея.
Попадая в один аквариум, мурены сражаются друг с другом, пока не останется ровно одна рыба. Когда сражаются две мурены, большая из них съедает меньшую (если их массы равны, то одна их них все равно съест другую). А именно, пусть изначально в аквариуме находятся \(n\) мурен, и \(i\)-я из них имеет массу \(x_i\). Тогда между ними произойдет \(n - 1\) сражение, в результате которых в живых останется только одна мурена. В сражении двух мурен с массами \(a\) и \(b\), где \(a \le b\), мурена массы \(a\) будет съедена и изчезнет из аквариума, а мурена массы \(b\) увеличит свою массу до \(a+b\).
Сражение между двумя муренами с массами \(a\) и \(b\), где \(a \le b\), считается опасным, если \(b \le 2 a\). Для данного множества мурен опасность определяется как максимальное число опасных сражений, которое может произойти среди этих мурен, если их поместить в один аквариум.
Сейчас Вася думает, каких именно мурен запустить в аквариум. У него есть некоторое множество мурен (изначально пустое). Он проделывает с ним серию операций. Каждой операцией он или добавляет новую мурену в множество, или удаляет. Вася просит вас посчитать опасность множества мурен после каждой операции.
Примечание
В третьем примере после выполнения всех операций множество мурен выглядит как \(\{1, 1, 4\}\). Для такого множества мурен существует несколько возможных вариантов развития событий, если их всех поместить в один аквариум:
- Мурена веса 4 съедает мурену веса 1, а затем вторую мурену веса 1. В этом случае ни одно из сражений не является опасным.
- Мурена веса 1 съедает мурену веса 1, и это сражение является опасным. Теперь в аквариуме плавают две мурены: веса 4 и веса 2. Большая их них из них съедает меньшую, и это сражение также является опасным. В этом случае общее число опасных сражений будет равно 2.
Таким образом, опасность данного множества мурен равна 2.