#include <bits/stdc++.h> using namespace std; void printVec(vector <int>& v) { cout << ">>"; for (int i : v) { cout << ' ' << i; } cout << endl; } struct Solve { int n; vector <int> a, pos; vector <vector <int>> v; int total_inversion; int Build(int at, int l, int r) { v[at] = vector <int> (r - l + 1); if (l == r) { v[at].front() = a[l]; } else { int mid = (l + r) / 2; Build(at * 2, l, mid); Build(at * 2 + 1, mid + 1, r); merge(v[at * 2].begin(), v[at * 2].end(), v[at * 2 + 1].begin(), v[at * 2 + 1].end(), v[at].begin()); } return at; } Solve(int n): n(n), a(n), pos(n), v(4 * n + 4), total_inversion(0) { for (int i = 0; i < n; i++) { cin >> a[i]; a[i] = n - a[i]; pos[a[i]] = i; } Build(1, 0, n - 1); } int Query(int at, int l, int r, int x, int y, int a, int b) { if (a >= b) { return 0; } if (l == x && r == y) { return max(int(lower_bound(v[at].begin(), v[at].end(), b) - upper_bound(v[at].begin(), v[at].end(), a)), 0); } else { int mid = (l + r) / 2, ret = 0; if (x <= mid) { ret += Query(at * 2, l, mid, x, min(y, mid), a, b); } if (mid + 1 <= y) { ret += Query(at * 2 + 1, mid + 1, r, max(x, mid + 1), y, a, b); } return ret; } } pair <int, int> BestPair() { set <int> s; int best = 0; pair <int, int> ret = { -1, -1}; vector <int> inv(n); set <int> valid; for (int i = n - 1, m = -2; i >= 0; --i) { if (a[i] > m + 1) { valid.insert(i); } m = max(m, a[i]); } auto valid_pos = [this, &inv, &best, &ret] () -> vector <int> { int best_inv = 0, j = pos[n - 1]; for (int i : pos) { if (i >= j) { continue; } inv[i] = Query(1, 0, n - 1, i, j, a[i], a[j]); best_inv = max(inv[i], best_inv); if (inv[i] > best) { best = inv[i]; ret = {i, j}; } else if (inv[i] == best) { ret = min(make_pair(i, j), ret); } } vector <bool> is_valid(n, false); for (int i = 0, m = n + 1; i < n; i++) { // is a[i] > min, not valid is_valid[i] = a[i] < m - 1; m = min(m, a[i]); } vector <int> vpos; for (int i : pos) { if (is_valid[i] && (i >= j || inv[i] == best_inv)) { vpos.push_back(i); } } return vpos; }(); for (int i : valid_pos) { int best_inv = 0; for (auto j = valid.upper_bound(i); j != valid.end(); j++) { inv[*j] = Query(1, 0, n - 1, i, *j, a[i], a[*j]); best_inv = max(inv[*j], best_inv); if (inv[*j] > best) { best = inv[*j]; ret = {i, *j}; } else if (inv[*j] == best) { ret = min(make_pair(i, *j), ret); } } vector <int> to_remove; for (auto j = valid.upper_bound(i); j != valid.end(); j++) { if (inv[*j] < best_inv - 1) { to_remove.push_back(*j); } } for (int j : to_remove) { valid.erase(j); } } for (int i = ret.first - 1, j = ret.second; i >= 0; i--) { if (best == Query(1, 0, n - 1, i, j, a[i], a[j])) { ret.first = i; } } for (int i = ret.first, j = ret.second - 1; j > i; j--) { if (best == Query(1, 0, n - 1, i, j, a[i], a[j])) { ret.second = j; } } if (best == 0) { vector <bool> r(n); for (int i = n - 1, m = -1; i >= 0; i--) { if (a[i] < m) { r[i] = true; } m = max(m, a[i]); } for (int i = 0; i < n; i++) { if (r[i]) { for (int j = i + 1; j < n; j++) { if (a[j] > a[i]) { return {i, j}; } } } } } // cout << best << endl; return ret; } }; int main(int argc, char const * argv[]) { ios::sync_with_stdio(false); int n; cin >> n; Solve S(n); auto best = [n, &S] () -> pair <int, int> { for (int i = 0; i < n - 1; i++) { if (S.a[i] != S.a[i + 1] + 1) { return S.BestPair(); } } return { -1, -1}; }(); if (best.first != -1) { cout << best.first + 1 << ' ' << best.second + 1 << endl; } else { cout << "Cool Array" << endl; } // int n; // cin >> n; // vector <int> a(n + 1); // vector <int> pos(n + 1); // for (int i = 1; i <= n; i++) { // cin >> a[i]; // a[i] = n - a[i] + 1; // pos[a[i]] = i; // } // printVec(a); // vector <vector <int>> u(n + 1, vector <int>(n + 1)); // vector <vector <int>> d(n + 1, vector <int>(n + 1)); // for (int i = 1; i <= n; i++) { // for (int j = 1; j <= n; j++) { // d[i][j] = u[i][j] + d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1]; // // for (int k = 1; k < j; k++) { // // d[i][j] += a[k] < a[i]; // // } // } // } // printMat(u); // printMat(d); // for (int i = 1; i <= n; i++) { // for (int j = i + 1; j <= n; j++) { // if (a[i] > a[j]) continue; // int l = pos[a[i] + 1]; // cout << "+> " << i << ' ' << j << ' ' // << 2 * (d[j][j] - d[l][j] - d[j][i + 1] + d[l][i + 1]) + (a[i] < a[j]) << endl; // auto b = a; // swap(b[i], b[j]); // cout << "+> " << i << ' ' << j << ' ' // << (inversion(n, a) - inversion(n, b)) << endl; // } // } return 0; }