Mali Đura je dobio sledeći zadatak. Njemu se donose prazni baloni i baloni sa vodom. Kad mu se donese prazan balon, postavlja se pitanje iz koliko najviše donetih balona sa vodom do sada može da istrese svu vodu u upravo doneti prazan balon. Da bi opisali zadatak koji je postavljen malom Đuri, definisaćemo dve operacije

• N v - donet je nov balon u kome se nalazi v litara vode
• Q v - donet je nov balon zapremine v litara, ali prazan. U tom momentu, mali Đura treba da odgovori iz koliko najviše do sada donetih balona može da se prespe voda u trenutno donešeni

Ulaz:

(Ulazni podaci se nalaze u datoteci baloni.in) U prvom redu se nalazi prirodan broj M (1 ≤ M ≤ 100.000) koji predstavlja broj operacija. U svakom od narednih M redova se nalaze operacije oblika C v, gde C {N, Q}. Ako C = N, tada 1 ≤ v ≤ 200.000. Ako C = Q, tada 1 ≤ v ≤ 100.000.000.

Izlaz:

(Izlazne podatke upisati u datoteku baloni.out) Za svaku operaciju oblika Q v, redom, u jedan red ispisati koliko najviše do sada donešenih balona sa vodom može da se isprazni u dati balon.

Primer 1:

9
Q 10
N 3
Q 10
N 7
Q 10
N 2
Q 10
N 3
Q 10

0
1
2
2
3

Objašnjenje.

Nakon donošenja prvog praznog balona, ne postoji ni jedan donet balon sa vodom, te nije moguće ni jedan presuti u isti. Nakon donošenja poslednjeg praznog balona u njega je moguće presuti vodu iz balona zapremina 3, 2 i 3, što je i najviše u ovom slučaju.

Primer 2:

10
N 5
N 8
N 1
Q 20
N 11
Q 8
N 1
N 2
Q 31
N 12

3
2
6

/*
  Author: Slobodan Mitrovic
  e-mail: boba5555@gmail.com
  date: 25.05.2009.
  Complexity: O(m log max_v) - in this case, max_v = 200000
*/
#include <iostream>
#include <cstdio>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)
#define all(_v) (_v).begin() , (_v).end()
#define sz size()
#define pb push_back
#define SET(__set, val) memset(__set, val, sizeof(__set))
#define FOR(__i, __n) ffor (__i, 0, __n)

using namespace std;

const int MAXVAL = 200002;
const int HIGHEST_BIT = 1 << 17;

int bit[MAXVAL];
long long bitWeight[MAXVAL]; // 100000 * 200000 > 2^32

void update(int idx){
  int weight = idx;
  while (idx < MAXVAL){
    bit[idx]++;
    bitWeight[idx] += weight;
    idx += (idx & -idx);
  }
}

struct mpair{
  long long a, b;
  mpair(){
  }

  mpair(long long _a, long long _b){
    a = _a;
    b = _b;
  }
};

mpair read(int idx){
  long long ret = 0, retW = 0;
  while (idx){
    ret += bit[idx];
    retW += bitWeight[idx];
    idx -= (idx & -idx);
  }

  return mpair(ret, retW);
}

int find(int cumFre){
  int ret = -1, idx = 0, bitMask = HIGHEST_BIT;

    while ((bitMask != 0) && (idx < MAXVAL)){
        int tIdx = idx + bitMask;
        if (tIdx < MAXVAL){
          if (cumFre > bitWeight[tIdx]){
             idx = tIdx;
             cumFre -= bitWeight[tIdx];
          }
          else
        ret = tIdx;
    }
        bitMask >>= 1;
    }

    return ret;
}

int main(){
    freopen("baloni.in", "rt", stdin);
    freopen("baloni.out", "wt", stdout);
    int M, v, ret, canTake, cntOpN = 0, idx;
    mpair rr;
    char op;
    scanf("%d", &M);
    SET(bit, 0);
    SET(bitWeight, 0);
    FOR (i, M){
    scanf("\n%c %d", &op, &v);
    if (op == 'N'){
      update(v);
      cntOpN++;
    }
    else{
      idx = find(v);
      if (idx == -1)
        printf("%d\n", cntOpN);
      else{
        rr = read(idx - 1);
        ret = rr.a;
        v -= rr.b;
        ret += v / idx;
        printf("%d\n", ret);
      }
    }
  }
  return 0;
}