#pragma comment (linker, "/STACK:1280000000") #define _CRT_SECURE_NO_WARNINGS //#include "testlib.h" #include <cstdio> #include <cassert> #include <algorithm> #include <iostream> #include <memory.h> #include <string> #include <vector> #include <set> #include <map> #include <cmath> #include <bitset> #include <deque> #include <unordered_map> #include <unordered_set> #include <ctime> #include <stack> #include <queue> #include <fstream> #include <sstream> using namespace std; //#define FILENAME "" #define mp make_pair #define all(a) a.begin(), a.end() typedef long long li; typedef long double ld; void solve(); void precalc(); clock_t start; //int timer = 1; int testNumber = 1; bool todo = true; int main() { #ifdef room111 freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #else //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); //freopen(FILENAME".in", "r", stdin); //freopen(FILENAME ".out", "w", stdout); #endif start = clock(); int t = 1; cout.sync_with_stdio(0); cin.tie(0); precalc(); cout.precision(10); cout << fixed; //cin >> t; int testNum = 1; while (t--) { //cout << "Case #" << testNum++ << ": "; solve(); ++testNumber; //++timer; } #ifdef room111 cerr << "\n\n" << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n"; #endif return 0; } //BE CAREFUL: IS INT REALLY INT? //#define int li /*int pr[] = { 97, 2011 }; int mods[] = { 1000000007, 1000000009 }; const int C = 100500; int powers[2][C];*/ //int MOD = 1000000007; //int c[5010][5010]; //int catalan[200500]; //ld doubleC[100][100]; int binpow(int q, int w, int mod) { if (!w) return 1 % mod; if (w & 1) return q * 1LL * binpow(q, w - 1, mod) % mod; return binpow(q * 1LL * q % mod, w / 2, mod); } /*int curMod = 1000000009; int fact[100500], revfact[100500]; int getC(int n, int k) { int res = fact[n] * revfact[n - k] % curMod * revfact[k] % curMod; return res; }*/ void precalc() { /*fact[0] = revfact[0] = 1; for (int i = 1; i < 100500; ++i) { fact[i] = fact[i - 1] * i % curMod; revfact[i] = binpow(fact[i], curMod - 2, curMod); }*/ /*for (int w = 0; w < 2; ++w) { powers[w][0] = 1; for (int j = 1; j < C; ++j) { powers[w][j] = (powers[w][j - 1] * 1LL * pr[w]) % mods[w]; } }*/ /*catalan[0] = 1; for (int n = 0; n < 200500 - 1; ++n) { catalan[n + 1] = catalan[n] * 2 * (2 * n + 1) % MOD * binpow(n + 2, MOD - 2, MOD) % MOD; }*/ /*for (int i = 0; i < 5010; ++i) { c[i][i] = c[i][0] = 1; for (int j = 1; j < i; ++j) { c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD; } }*/ /*for (int i = 0; i < 100; ++i) { doubleC[i][i] = doubleC[i][0] = 1.0; for (int j = 1; j < i; ++j) { doubleC[i][j] = doubleC[i - 1][j - 1] + doubleC[i - 1][j]; } }*/ } int gcd(int q, int w) { while (w) { q %= w; swap(q, w); } return q; } //#define int li //int mod = 1000000007; struct Node { int mx; int add; int mxPos; Node() {} Node(int mx, int add, int mxPos) :mx(mx), add(add), mxPos(mxPos) {} }; const int shift = 1 << 19; Node tree[2 * shift + 5]; void push(int v) { for (int h = 0; h < 2; ++h) { tree[2 * v + h].add += tree[v].add; } tree[v].mx += tree[v].add; tree[v].add = 0; } Node merge(const Node& q, const Node& w) { Node res(max(q.mx + q.add, w.mx + w.add), 0, w.mxPos); if (res.mx == q.mx + q.add) { res.mxPos = q.mxPos; } return res; } int n; void build(int v, int tl, int tr) { if (tl + 1 == tr) { tree[v] = Node(0, 0, tl); return; } int tm = (tl + tr) / 2; build(2 * v, tl, tm); build(2 * v + 1, tm, tr); tree[v] = merge(tree[2 * v], tree[2 * v + 1]); } void modify(int v, int tl, int tr, int l, int r, int val) { if (r <= tl || tr <= l) { return; } if (l <= tl && tr <= r) { tree[v].add += val; return; } push(v); int tm = (tl + tr) / 2; modify(2 * v, tl, tm, l, r, val); modify(2 * v + 1, tm, tr, l, r, val); tree[v] = merge(tree[2 * v], tree[2 * v + 1]); } Node rmq(int v, int tl, int tr, int l, int r) { if (r <= tl || tr <= l) { return Node(0, 0, tl); } if (l <= tl && tr <= r) { return tree[v]; } push(v); int tm = (tl + tr) / 2; Node res = merge(rmq(2 * v, tl, tm, l, r), rmq(2 * v + 1, tm, tr, l, r)); tree[v] = merge(tree[2 * v], tree[2 * v + 1]); return res; } Node getMax(int l, int r) { return rmq(1, 0, n, l, r); } void update(int l, int r, int val) { modify(1, 0, n, l, r, val); } bool compSec(const pair<int, int>& q, const pair<int, int>& w) { return mp(q.second, q.first) < mp(w.second, w.first); } void solve() { cin >> n; vector<int> p(n); for (int i = 0; i < n; ++i) { cin >> p[i]; } bool f = true; for (int i = 0; i + 1 < n; ++i) { if (p[i] > p[i + 1]) { f = false; break; } } if (f) { cout << "Cool Array\n"; return; } vector<char> used(n, false); used[0] = used[n - 1] = true; vector<pair<int, int>> leftPos; leftPos.push_back(mp(0, p[0])); for (int i = 1; i < n; ++i) { if (p[i] > leftPos.back().second) { leftPos.push_back(mp(i, p[i])); used[i] = true; } } vector<pair<int, int>> rightPos; rightPos.push_back(mp(n - 1, p[n - 1])); for (int i = n - 2; i >= 0; --i) { if (p[i] < rightPos.back().second) { rightPos.push_back(mp(i, p[i])); used[i] = true; } } reverse(all(rightPos)); vector <vector<pair<pair<int, int>, int>>> events(leftPos.size() + 1); for (int i = 0; i < n; ++i) { if (used[i]) { continue; } int startX = upper_bound(all(leftPos), mp(i, p[i]), compSec) - leftPos.begin(); int finishX = lower_bound(all(leftPos), mp(i, p[i])) - leftPos.begin(); int startY = upper_bound(all(rightPos), mp(i, p[i])) - rightPos.begin(); int finishY = lower_bound(all(rightPos), mp(i, p[i]), compSec) - rightPos.begin(); if (finishX > startX && finishY > startY) { events[startX].push_back(mp(mp(startY, finishY), 1)); events[finishX].push_back(mp(mp(startY, finishY), -1)); } } build(1, 0, n); int bestAdd = -1; int bestI = -1, bestJ = -1; for (int i = 0; i < leftPos.size(); ++i) { for (auto item : events[i]) { update(item.first.first, item.first.second, item.second); } Node curMax = getMax(0, rightPos.size()); int curAdd = curMax.add + curMax.mx; if (curAdd > bestAdd) { bestAdd = curAdd; bestI = leftPos[i].first; bestJ = rightPos[curMax.mxPos].first; } } if (bestAdd == 0) { for (int i = 0; i < n; ++i) { if (p[i] != i + 1) { for (int j = i + 1; j < n; ++j) { if (p[i] > p[j]) { cout << i + 1 << ' ' << j + 1 << "\n"; return; } } } } } if (bestAdd == -1) { cout << "Cool Array\n"; } else { cout << bestI + 1 << ' ' << bestJ + 1 << "\n"; } }