aoj-1351.cpp

#include "../include/structure/starry_sky_tree.cpp"
#include "../include/template/range.cpp"

using namespace std;

char s[301000];

int main() {
  int N, Q, p;
  scanf("%d%d%s", &N, &Q, s);
  StarrySkyTree<int> seg(N);
  set<int> right;
  for (int i : range(N)) {
    if (s[i] == '(') {
      seg.update(i, N, 1);
    }
    else {
      seg.update(i, N, -1);
      right.insert(i);
    }
  }
  while (Q--) {
    scanf("%d", &p);
    --p;
    if (right.find(p) == end(right)) {
      right.insert(p);
      int l = *begin(right);
      seg.update(l, p, 2);
      right.erase(l);
      cout << l + 1 << endl;
    }
    else {
      right.erase(p);
      seg.update(p, N, 2);
      int lb = -1, ub = N;
      while (ub - lb > 1) {
        const int mid = (lb + ub) / 2;
        if (seg.query(mid, N) >= 2)
          ub = mid;
        else
          lb = mid;
      }
      seg.update(ub, N, -2);
      right.insert(ub);
      cout << ub + 1 << endl;
    }
  }
  return 0;
}