#include <bits/stdc++.h>
using namespace std;
long long int a[200005];
int main() {
  int q, id, ans;
  char c;
  int l = -1;
  int r = -1;
  cin >> q;
  while (q--) {
    cin >> c >> id;
    if (c != '?') {
      if (l == -1 && r == -1) {
        a[id] = 0;
        l = r = 0;
      } else {
        if (c == 'L') {
          l--;
          a[id] = l;
        } else {
          r++;
          a[id] = r;
        }
      }
    } else {
      ans = min(a[id] - l, r - a[id]);
      cout << ans << '\n';
    }
  }
  return 0;
}
