#include<iostream> #include<algorithm> #include<vector> #define f first #define s second #define mp make_pair #define INF 1000000000 using namespace std; struct node { int l, r; int cadd; pair<int, int> cmax; node *lch, *rch; void update() { cmax = mp(0, cmax.s); if(lch != 0) cmax = max(cmax, lch->cmax); if(rch != 0) cmax = max(cmax, rch->cmax); cmax.f += cadd; } node() {lch = 0, rch = 0, cadd = 0, cmax = mp(0, 0); } }; //------------------------------------------------------------------------ //Segment tree function here template<int N> struct segtree { node vert[N]; void init(int l = 0, int r = N/2, int cind = 0) { int mid = (r + l) / 2; vert[cind].l = l; vert[cind].r = r; vert[cind].cmax.s = -l; if(r - l == 1) return; vert[cind].lch = &vert[cind*2 + 1]; vert[cind].rch = &vert[cind*2 + 2]; init(l, mid, cind * 2 + 1); init(mid, r, cind * 2 + 2); } //Here we implement the range update functions and query function void rangeadd(int l, int r, int toadd, int cind = 0) { node* cur = &vert[cind]; if(cur->l >= l && cur->r <= r) { cur->cadd += toadd; cur->update(); return; } if(cur->r <= l || cur->l >= r) return; rangeadd(l, r, toadd, cind * 2 + 1); rangeadd(l, r, toadd, cind * 2 + 2); cur->update(); } pair<int, int> getmax(int l, int r, int toadd = 0, int cind = 0) { node* cur = &vert[cind]; if(cur->l >= l && cur->r <= r) return mp(toadd + cur->cmax.f, cur->cmax.s); if(cur->r <= l || cur->l >= r) return mp(-INF, 0); return max(getmax(l, r, toadd + cur->cadd, cind * 2 + 1) , getmax(l, r, toadd + cur->cadd, cind * 2 + 2) ); } }; //---------------------------------------------------------------------------------- //Main algorithm begins here int n, p1; vector<pair<int, int> > upperleft, lowerright, yfirst, xfirst; vector<pair<int, int> > uly; segtree<1048576> st; //Assumes x-first ordering pair<int, int> ulinfluence(pair<int, int> pt) { int sind = upper_bound(uly.begin(), uly.end(), mp(pt.s, INF) ) - uly.begin(); int eind = lower_bound(upperleft.begin(), upperleft.end(), pt) - upperleft.begin(); return mp(sind, eind); } int main() { cin.sync_with_stdio(false); st.init(); cin >> n; for(int i=0;i<n;i++) { cin >> p1; xfirst.push_back(mp(i, p1-1) ); yfirst.push_back(mp(p1-1, i) ); } sort(yfirst.begin(), yfirst.end() ); //Next we initialize upperleft and lowerright arrays uly.push_back(mp(xfirst[0].s, upperleft.size() ) ); upperleft.push_back(xfirst[0]); for(int i=1;i<n;i++) { if(upperleft.back().s < xfirst[i].s) { uly.push_back(mp(xfirst[i].s, upperleft.size() ) ); upperleft.push_back(xfirst[i]); } } sort(uly.begin(), uly.end() ); lowerright.push_back(xfirst[n-1]); for(int i=n-2; i>=0; i--) if(lowerright.back().s > xfirst[i].s) lowerright.push_back(xfirst[i]); //Finally we start iterating over the lowerright values int yind = n-1, xind = n-1; pair<int, pair<int, int> > result = mp(-1, mp(-1, -1) ); for(unsigned int lrind = 0; lrind < lowerright.size(); lrind++) { //First fix the upper values while(yfirst[yind].f > lowerright[lrind].s) { pair<int, int> seg = ulinfluence(mp(yfirst[yind].s, yfirst[yind].f) ); st.rangeadd(seg.f, seg.s, 1); yind--; } //Next fix the lower values while(xfirst[xind].f > lowerright[lrind].f) { pair<int, int> seg = ulinfluence(xfirst[xind]); st.rangeadd(seg.f, seg.s, -1); xind--; } //Finally add the value to the result pair<int, int> seg = ulinfluence(lowerright[lrind]); pair<int, int> mval = st.getmax(seg.f, seg.s); result = max(result, mp(mval.f, mp(-upperleft[-mval.s].f, -lowerright[lrind].f) ) ); } //Finally we are ready to output the result if(result.f == -1) cout << "Cool Array\n"; else cout << -result.s.f + 1 << ' ' << -result.s.s + 1 << '\n'; return 0; }