ヒープの再構築で行われる交換回数

最初は空のヒープが用意されており、そこに対して q 個のクエリを処理することを求められます。クエリには2種類あります:

1. add x - ヒープに x を追加する

2. pop - ヒープの根（ルート）を削除する

各クエリに対して、ヒープが最大ヒープ特性を満たすように再構築を行う際に必要な交換操作の回数を出力してください。

なお、pop を実行する場合、根とヒープの末尾の要素を入れ替える操作も交換回数に含まれます。

入力

最初の行には整数 q (1 ≤ q ≤ ) が1つ与えられます。

続く q 行にはクエリが1行に1つずつ与えられます。すべての add クエリにおいて、x の絶対値は を超えないことが保証されています。

出力

各クエリに対して、必要な交換回数を1行ずつ出力してください。

例