#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
template<class Monoid>
class SegTree {
private:
using T = typename Monoid::T;
Monoid op;
const int n;
vector<T> t;
void prop_to(int i) { t[i] = op(t[2*i], t[2*i+1]); }
public:
SegTree(int n) : n(n), t(2*n, op.identity()) {}
SegTree(const vector<T>& v) : n(v.size()), t(2*n) {
copy(begin(v), end(v), begin(t) + n);
for (int i = n-1; i > 0; --i) prop_to(i);
}
void set(int i, const T& x) {
t[i += n] = x;
while (i >>= 1) prop_to(i);
}
T get(int i) { return t[i + n]; }
T accumulate(int l, int r) {
T accl = op.identity(), accr = op.identity();
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) accl = op(accl, t[l++]);
if (r & 1) accr = op(t[r-1], accr);
}
return op(accl, accr);
}
};
struct RMQ {
using T = int;
T operator()(const T& a, const T& b) { return a < b ? a : b; }
static constexpr T identity() { return INT_MAX; }
};
int main() {
int n = 1e7;
vector<int> a(n);
rep(i, n) a[i] = i;
SegTree<RMQ> rmq(a);
bool f = true;
rep(i, n) {
int l = rand()%n, r = rand()%n;
if (l == r) continue;
if (l > r) swap(l, r);
f &= rmq.accumulate(l, r) == l;
}
cout << (f ? "OK" : "NG") << endl;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIHJlcChpLCBuKSBmb3IgKGludCBpID0gMDsgaSA8IChuKTsgKytpKQoKdGVtcGxhdGU8Y2xhc3MgTW9ub2lkPgpjbGFzcyBTZWdUcmVlIHsKcHJpdmF0ZToKCXVzaW5nIFQgPSB0eXBlbmFtZSBNb25vaWQ6OlQ7CglNb25vaWQgb3A7Cgljb25zdCBpbnQgbjsKCXZlY3RvcjxUPiB0OwoKCXZvaWQgcHJvcF90byhpbnQgaSkgeyB0W2ldID0gb3AodFsyKmldLCB0WzIqaSsxXSk7IH0KCnB1YmxpYzoKCVNlZ1RyZWUoaW50IG4pIDogbihuKSwgdCgyKm4sIG9wLmlkZW50aXR5KCkpIHt9CglTZWdUcmVlKGNvbnN0IHZlY3RvcjxUPiYgdikgOiBuKHYuc2l6ZSgpKSwgdCgyKm4pIHsKCQljb3B5KGJlZ2luKHYpLCBlbmQodiksIGJlZ2luKHQpICsgbik7CgkJZm9yIChpbnQgaSA9IG4tMTsgaSA+IDA7IC0taSkgcHJvcF90byhpKTsKCX0KCgl2b2lkIHNldChpbnQgaSwgY29uc3QgVCYgeCkgewoJCXRbaSArPSBuXSA9IHg7CgkJd2hpbGUgKGkgPj49IDEpIHByb3BfdG8oaSk7Cgl9CgoJVCBnZXQoaW50IGkpIHsgcmV0dXJuIHRbaSArIG5dOyB9CgoJVCBhY2N1bXVsYXRlKGludCBsLCBpbnQgcikgewoJCVQgYWNjbCA9IG9wLmlkZW50aXR5KCksIGFjY3IgPSBvcC5pZGVudGl0eSgpOwoJCWZvciAobCArPSBuLCByICs9IG47IGwgPCByOyBsID4+PSAxLCByID4+PSAxKSB7CgkJCWlmIChsICYgMSkgYWNjbCA9IG9wKGFjY2wsIHRbbCsrXSk7CgkJCWlmIChyICYgMSkgYWNjciA9IG9wKHRbci0xXSwgYWNjcik7CgkJfQoJCXJldHVybiBvcChhY2NsLCBhY2NyKTsKCX0KfTsKCnN0cnVjdCBSTVEgewoJdXNpbmcgVCA9IGludDsKCVQgb3BlcmF0b3IoKShjb25zdCBUJiBhLCBjb25zdCBUJiBiKSB7IHJldHVybiBhIDwgYiA/IGEgOiBiOyB9CglzdGF0aWMgY29uc3RleHByIFQgaWRlbnRpdHkoKSB7IHJldHVybiBJTlRfTUFYOyB9Cn07CgppbnQgbWFpbigpIHsKCWludCBuID0gMWU3OwoJdmVjdG9yPGludD4gYShuKTsKCXJlcChpLCBuKSBhW2ldID0gaTsKCVNlZ1RyZWU8Uk1RPiBybXEoYSk7Cglib29sIGYgPSB0cnVlOwoJcmVwKGksIG4pIHsKCQlpbnQgbCA9IHJhbmQoKSVuLCByID0gcmFuZCgpJW47CgkJaWYgKGwgPT0gcikgY29udGludWU7CgkJaWYgKGwgPiByKSBzd2FwKGwsIHIpOwoJCWYgJj0gcm1xLmFjY3VtdWxhdGUobCwgcikgPT0gbDsKCX0KCWNvdXQgPDwgKGYgPyAiT0siIDogIk5HIikgPDwgZW5kbDsKfQo=