#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
const int sqrtN = 700;
// const int sqrtN = 1;
struct SqrtDecomposition {
  int N, K;
  vector<bool> data;
  // 0, 1, -1 (unknown)
  vector<char> reader;
  vector<char> writer;
  SqrtDecomposition(int n) : N(n) {
    K = (N + sqrtN - 1) / sqrtN;
    data.assign(K * sqrtN, false);
    reader.assign(K, 0);
    writer.assign(K, -1);
  }
  void set1(int x) {
    int k = x / sqrtN;
    int l = k * sqrtN, r = (k + 1) * sqrtN;
    if(writer[k] != -1) {
      for(int i = l; i < r; ++i) {
        data[i] = writer[k];
      }
    }
    writer[k] = -1;
    data[x] = 1;
    bool all0 = true, all1 = true;
    for(int i = l; i < r; ++i) {
      if(data[i] == 1) all0 = false;
      else all1 = false;
    }
    if(all0) {
      reader[k] = 0;
    }
    else if(all1) {
      reader[k] = 1;
    }
    else {
      reader[k] = -1;
    }
  }
  void set0range(int a, int b) {
    for(int k = 0; k < K; ++k) {
      int l = k * sqrtN, r = (k + 1) * sqrtN;
      if(r <= a || b <= l) continue;
      if(a <= l && r <= b) {
        writer[k] = 0;
        reader[k] = 0;
      }
      else {
        if(writer[k] != -1) {
          for(int i = l; i < r; ++i) {
            data[i] = writer[k];
          }
        }
        writer[k] = -1;
        for(int i = max(a, l); i < min(b, r); ++i) {
          data[i] = 0;
        }
        bool all0 = true, all1 = true;
        for(int i = l; i < r; ++i) {
          if(data[i] == 1) all0 = false;
          else all1 = false;
        }
        if(all0) {
          reader[k] = 0;
        }
        else if(all1) {
          reader[k] = 1;
        }
        else {
          reader[k] = -1;
        }
      }
    }
  }
  int search(int x) {
    for(int k = x / sqrtN; k >= 0; --k) {
      // DEBUG(k);
      int l = k * sqrtN, r = (k + 1) * sqrtN;
      // DEBUG(l);
      // DEBUG(r);
      if(reader[k] == 1) continue;
      else if(reader[k] == 0) return min(x, r - 1);
      else {
        for(int i = min(r - 1, x); i >= l; --i) {
          // cerr << "data[" << i << "] = " << data[i] << endl;
          if(data[i] == 0) return i;
        }
      }
    }
    return -1;
  }
  bool check0(int x) {
    for(int k = 0; k < K; ++k) {
      int l = k * sqrtN, r = (k + 1) * sqrtN;
      if(r <= x) continue;
      if(x <= l) {
        if(reader[k] != 0) return false;
      }
      else {
        for(int i = max(x, l); i < r; ++i) {
          if(data[i] != 0) return false;
        }
      }
    }
    return true;
  }
  void dump() {
    cerr << "data[] =";
    REP(i,N) {
      cerr << " " << (int)data[i];
    }
    cerr << endl;

    cerr << "reader[] =";
    REP(i,K) {
      cerr << " " << (int)reader[i];
    }
    cerr << endl;

    cerr << "writer[] =";
    REP(i,K) {
      cerr << " " << (int)writer[i];
    }
    cerr << endl;
  }
};
void dbg() {
  SqrtDecomposition decomp(10);
  DEBUG(decomp.search(2));
  decomp.set1(2);
  decomp.set0range(3, 3);
  decomp.dump();

  DEBUG(decomp.search(3));
  decomp.set1(3);
  decomp.set0range(4, 4);
  decomp.dump();

  DEBUG(decomp.search(1));
  decomp.set1(1);
  decomp.set0range(2, 2);
  decomp.dump();

  DEBUG(decomp.search(1));
  decomp.dump();
  DEBUG(decomp.check0(1));
  // decomp.set1(1);
}
signed main() {
  if(false) {
    dbg();
  }
  else {
    ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> query(N);
    REP(i,N) cin >> query[i];
    SqrtDecomposition decomp(600001);
    bool nomore = false;
    REP(i,N) {
      int x = query[i];
      if(x >= 600000) {
        cout << "Yes" << endl;
        decomp.set1(600000);
      }
      else {
        int s = decomp.search(x);
        // DEBUG(x);
        // DEBUG(s);
        // DEBUG(decomp.check0(x + 1));
        // decomp.dump();
        if(nomore) {
          cout << "No" << endl;
        }
        else if(s == -1) {
          cout << "No" << endl;
        }
        else if(s == 0 && decomp.check0(x + 1) == false) {
          cout << "No" << endl;
        }
        else {
          decomp.set1(s);
          decomp.set0range(s + 1, x + 1);
          cout << "Yes" << endl;
          if(s == 0) nomore = true;
        }
      }
    }
  }
}
### Prompt

Construct a cpp code solution to the problem outlined:

Example

Input

6
2
3
1
1
4
2


Output

Yes
Yes
Yes
No
Yes
No

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
const int sqrtN = 700;
// const int sqrtN = 1;
struct SqrtDecomposition {
  int N, K;
  vector<bool> data;
  // 0, 1, -1 (unknown)
  vector<char> reader;
  vector<char> writer;
  SqrtDecomposition(int n) : N(n) {
    K = (N + sqrtN - 1) / sqrtN;
    data.assign(K * sqrtN, false);
    reader.assign(K, 0);
    writer.assign(K, -1);
  }
  void set1(int x) {
    int k = x / sqrtN;
    int l = k * sqrtN, r = (k + 1) * sqrtN;
    if(writer[k] != -1) {
      for(int i = l; i < r; ++i) {
        data[i] = writer[k];
      }
    }
    writer[k] = -1;
    data[x] = 1;
    bool all0 = true, all1 = true;
    for(int i = l; i < r; ++i) {
      if(data[i] == 1) all0 = false;
      else all1 = false;
    }
    if(all0) {
      reader[k] = 0;
    }
    else if(all1) {
      reader[k] = 1;
    }
    else {
      reader[k] = -1;
    }
  }
  void set0range(int a, int b) {
    for(int k = 0; k < K; ++k) {
      int l = k * sqrtN, r = (k + 1) * sqrtN;
      if(r <= a || b <= l) continue;
      if(a <= l && r <= b) {
        writer[k] = 0;
        reader[k] = 0;
      }
      else {
        if(writer[k] != -1) {
          for(int i = l; i < r; ++i) {
            data[i] = writer[k];
          }
        }
        writer[k] = -1;
        for(int i = max(a, l); i < min(b, r); ++i) {
          data[i] = 0;
        }
        bool all0 = true, all1 = true;
        for(int i = l; i < r; ++i) {
          if(data[i] == 1) all0 = false;
          else all1 = false;
        }
        if(all0) {
          reader[k] = 0;
        }
        else if(all1) {
          reader[k] = 1;
        }
        else {
          reader[k] = -1;
        }
      }
    }
  }
  int search(int x) {
    for(int k = x / sqrtN; k >= 0; --k) {
      // DEBUG(k);
      int l = k * sqrtN, r = (k + 1) * sqrtN;
      // DEBUG(l);
      // DEBUG(r);
      if(reader[k] == 1) continue;
      else if(reader[k] == 0) return min(x, r - 1);
      else {
        for(int i = min(r - 1, x); i >= l; --i) {
          // cerr << "data[" << i << "] = " << data[i] << endl;
          if(data[i] == 0) return i;
        }
      }
    }
    return -1;
  }
  bool check0(int x) {
    for(int k = 0; k < K; ++k) {
      int l = k * sqrtN, r = (k + 1) * sqrtN;
      if(r <= x) continue;
      if(x <= l) {
        if(reader[k] != 0) return false;
      }
      else {
        for(int i = max(x, l); i < r; ++i) {
          if(data[i] != 0) return false;
        }
      }
    }
    return true;
  }
  void dump() {
    cerr << "data[] =";
    REP(i,N) {
      cerr << " " << (int)data[i];
    }
    cerr << endl;

    cerr << "reader[] =";
    REP(i,K) {
      cerr << " " << (int)reader[i];
    }
    cerr << endl;

    cerr << "writer[] =";
    REP(i,K) {
      cerr << " " << (int)writer[i];
    }
    cerr << endl;
  }
};
void dbg() {
  SqrtDecomposition decomp(10);
  DEBUG(decomp.search(2));
  decomp.set1(2);
  decomp.set0range(3, 3);
  decomp.dump();

  DEBUG(decomp.search(3));
  decomp.set1(3);
  decomp.set0range(4, 4);
  decomp.dump();

  DEBUG(decomp.search(1));
  decomp.set1(1);
  decomp.set0range(2, 2);
  decomp.dump();

  DEBUG(decomp.search(1));
  decomp.dump();
  DEBUG(decomp.check0(1));
  // decomp.set1(1);
}
signed main() {
  if(false) {
    dbg();
  }
  else {
    ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> query(N);
    REP(i,N) cin >> query[i];
    SqrtDecomposition decomp(600001);
    bool nomore = false;
    REP(i,N) {
      int x = query[i];
      if(x >= 600000) {
        cout << "Yes" << endl;
        decomp.set1(600000);
      }
      else {
        int s = decomp.search(x);
        // DEBUG(x);
        // DEBUG(s);
        // DEBUG(decomp.check0(x + 1));
        // decomp.dump();
        if(nomore) {
          cout << "No" << endl;
        }
        else if(s == -1) {
          cout << "No" << endl;
        }
        else if(s == 0 && decomp.check0(x + 1) == false) {
          cout << "No" << endl;
        }
        else {
          decomp.set1(s);
          decomp.set0range(s + 1, x + 1);
          cout << "Yes" << endl;
          if(s == 0) nomore = true;
        }
      }
    }
  }
}
```