Вася — большой любитель рыб, и родители подарили ему на Новый Год аквариум. Вася не имеет ученой степени по ихтиологии, поэтому считает, что заполнить новый аквариум муренами — неплохая идея. К сожалению, мурены — хищные рыбы, поэтому Вася решил выяснить, насколько опасна эта затея.

Попадая в один аквариум, мурены сражаются друг с другом, пока не останется ровно одна рыба. Когда сражаются две мурены, большая из них съедает меньшую (если их массы равны, то одна их них все равно съест другую). А именно, пусть изначально в аквариуме находятся $$$n$$$ мурен, и $$$i$$$-я из них имеет массу $$$x_i$$$. Тогда между ними произойдет $$$n - 1$$$ сражение, в результате которых в живых останется только одна мурена. В сражении двух мурен с массами $$$a$$$ и $$$b$$$, где $$$a \le b$$$, мурена массы $$$a$$$ будет съедена и изчезнет из аквариума, а мурена массы $$$b$$$ увеличит свою массу до $$$a+b$$$.

Сражение между двумя муренами с массами $$$a$$$ и $$$b$$$, где $$$a \le b$$$, считается опасным, если $$$b \le 2 a$$$. Для данного множества мурен опасность определяется как максимальное число опасных сражений, которое может произойти среди этих мурен, если их поместить в один аквариум.

Сейчас Вася думает, каких именно мурен запустить в аквариум. У него есть некоторое множество мурен (изначально пустое). Он проделывает с ним серию операций. Каждой операцией он или добавляет новую мурену в множество, или удаляет. Вася просит вас посчитать опасность множества мурен после каждой операции.