#include <iostream> #include <climits> #include <vector> #include <deque> #include <random> #include <algorithm> using namespace std; mt19937 rng(1337); constexpr int N = 1 << 19; struct Node { Node* left; Node* right; int sum; }; deque<Node> nodes_; Node* createNode(Node* left, Node* right, int sum) { nodes_.emplace_back(); Node* ret = &nodes_.back(); ret->left = left; ret->right = right; ret->sum = sum; return ret; } Node* set(int x, Node* node, int sz = N) { if(x < 0 || x >= sz) return node; if(sz == 1) { return createNode(nullptr, nullptr, node->sum + 1); } int hsz = sz / 2; return createNode( set(x, node->left, hsz), set(x - hsz, node->right, hsz), node->sum + 1 ); } int query(int a, int b, Node* node, int sz = N) { if(b <= 0 || a >= sz) return 0; if(a <= 0 && b >= sz) return node->sum; int hsz = sz / 2; return query(a, b, node->left, hsz) + query(a - hsz, b - hsz, node->right, hsz); } Node* create(int sz = N) { if(sz == 1) { return createNode(nullptr, nullptr, 0); } else { Node* ch = create(sz / 2); return createNode(ch, ch, 0); } } int A[N]; Node* S[N + 1]; int cnt(int i1, int i2, int j1, int j2) { ++i2; ++j2; int ret = query(j1, j2, S[i2]) - query(j1, j2, S[i1]); return ret; } int main() { cin.sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; S[0] = create(); bool cool = true; for(int i = 0; i < n; ++i) { cin >> A[i]; --A[i]; if(A[i] != i) cool = false; S[i + 1] = set(A[i], S[i]); } if(cool) { cout << "Cool Array\n"; return 0; } vector<int> P; vector<int> Q; for(int i = 0; i < n; ++i) { if(cnt(0, i, A[i], n - 1) == 1) P.push_back(i); if(cnt(i, n - 1, 0, A[i]) == 1) Q.push_back(i); } auto asd = [&](int Pi, int Qi) { if(P[Pi] > Q[Qi]) return 0; if(A[P[Pi]] < A[Q[Qi]]) return 0; return cnt(P[Pi], Q[Qi], A[Q[Qi]], A[P[Pi]]); }; if(n < 1000) { int gaa = -1; int asdi = -1; int asdj = -1; for(int i = 0; i < (int)P.size(); ++i) { for(int j = 0; j < (int)Q.size(); ++j) { int val = asd(i, j); if(val > gaa) { gaa = val; asdi = P[i]; asdj = Q[j]; } } } cout << asdi + 1 << ' ' << asdj + 1 << '\n'; return 0; } reverse(P.begin(), P.end()); reverse(Q.begin(), Q.end()); int Qi = -1; int asdfa = -1; for(int fuu = 0; fuu < (int)Q.size(); ++fuu) { int val = asd(0, fuu); if(val > asdfa) { asdfa = val; Qi = fuu; } } int ret = -1; int reta = -1; int retb = -1; for(int Pi = 0; Pi < (int)P.size(); ++Pi) { int val = asd(Pi, Qi); // cout << P[Pi] << Q[Qi] << ": " << val << '\n'; if(P[Pi] != Q[Qi] && val >= ret) { ret = val; reta = Pi; retb = Qi; } while(Qi != (int)Q.size() - 1 && asd(Pi, Qi + 1) >= asd(Pi, Qi)) { ++Qi; int val = asd(Pi, Qi); // cout << P[Pi] << Q[Qi] << ": " << val << '\n'; if(P[Pi] != Q[Qi] && val >= ret) { ret = val; reta = Pi; retb = Qi; } } } while(retb < Q.size() - 1 && asd(reta, retb + 1) == asd(reta, retb)) ++retb; cout << P[reta] + 1 << ' ' << Q[retb] + 1 << '\n'; return 0; }