#include <algorithm> #include <iostream> #include <sstream> #include <utility> #include <cstdlib> #include <cstring> #include <cassert> #include <fstream> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <stack> #include <map> #include <set> using namespace std; #define pb push_back #define ppb pop_back #define mp make_pair #define fs first #define sc second #define abs(a) ((a) < 0 ? -(a) : (a)) #define sqr(a) ((a) * (a)) typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; const double eps = 1e-9; const int mod = (int)1e+9 + 7; const double pi = acos(-1.); const int maxn = 500100; int a[maxn], b[maxn]; vector<pair<int, int> > ub, vz; int ubval[maxn], vzval[maxn]; bool pm[maxn]; void bins1(int val) { int l = -1, r = ub.size() - 1; while(l + 1 < r) { int m = (l + r) >> 1; if(ub[m].sc > val) { r = m; } else { l = m; } } // cout << r << endl; ubval[r]++; } void bins2(int val) { int l = 0, r = vz.size(); while(l + 1 < r) { int m = (l + r) >> 1; if(vz[m].sc > val) { r = m; } else { l = m; } } // cout << r << endl; vzval[r]--; } int main() { #ifdef SOL { // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); } #else { srand(time(0)); const string file = ""; if(!file.empty()) { freopen((file + ".in").c_str(), "r", stdin); freopen((file + ".out").c_str(), "w", stdout); } } #endif bool ok = 1; int n; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); a[i]--; if(a[i] != i) ok = 0; b[a[i]] = i; } if(ok) { printf("Cool Array\n"); return(0); } { int xx = -1; for(int i = 0; i < n; i++) { if(b[i] > xx) { vz.pb(mp(b[i], i)); pm[b[i]] = 1; xx = b[i]; } } sort(vz.begin(), vz.end()); } { int xx = n; for(int i = n - 1; i >= 0; i--) { if(b[i] < xx) { ub.pb(mp(b[i], i)); pm[b[i]] = 1; xx = b[i]; } } sort(ub.begin(), ub.end()); } for(int i = 0; i < n; i++) { if(!pm[i]) { ubval[lower_bound(ub.begin(), ub.end(), mp(i, 0)) - ub.begin()]--; // cout << lower_bound(ub.begin(), ub.end(), mp(i, 0)) - ub.begin() << " "; bins1(a[i]); vzval[lower_bound(vz.begin(), vz.end(), mp(i, 0)) - vz.begin()]++; // cout << lower_bound(vz.begin(), vz.end(), mp(i, 0)) - vz.begin() << " "; bins2(a[i]); } } int lans = -1, lval = -1; { int ps = 0; for(int i = 0; i < ub.size(); i++) { ps += ubval[i]; if(lval < ps) { lval = ps; lans = i; } } } int rans = -1, rval = -1; { int ps = 0; for(int i = 0; i < vz.size(); i++) { ps += vzval[i]; if(rval < ps) { rval = ps; rans = i; } } } if(ub[lans].fs == vz[rans].fs) { int ansl, ansr, i; for(i = 0; i < n; i++) { if(i != a[i]) { ansl = i; break; } } for(i++; i < n; i++) { if(a[i] < a[ansl]) { ansr = i; break; } } printf("%d %d\n", ansl + 1, ansr + 1); } else { // assert(a[ub[lans].fs] > a[vz[rans].fs]); if(a[ub[lans].fs] <= a[vz[rans].fs]) { rans = -1, rval = -1; { int ps = 0; for(int i = 0; i < vz.size(); i++) { ps += vzval[i]; if(rval < ps && a[ub[lans].fs] > a[vz[i].fs]) { rval = ps; rans = i; } } } } printf("%d %d\n", ub[lans].fs + 1, vz[rans].fs + 1); } return(0); } // by Kim Andrey