/* */ //#pragma comment(linker, "/STACK:16777216") #include <fstream> #include <iostream> #include <string> #include <complex> #include <math.h> #include <set> #include <vector> #include <map> #include <queue> #include <stdio.h> #include <stack> #include <algorithm> #include <list> #include <ctime> #include <memory.h> #include <ctime> #include <assert.h> #define y0 sdkfaslhagaklsldk #define y1 aasdfasdfasdf #define yn askfhwqriuperikldjk #define j1 assdgsdgasghsf #define tm sdfjahlfasfh #define lr asgasgash #define eps 1e-6 #define M_PI 3.141592653589793 #define bs 1000000007 #define bsize 512 #define prev asdfasdf using namespace std; int n,ar[1<<20]; set<pair<int, int> > by_X,by_Y; set<pair<int, int> > ::iterator it; pair<int, int> prev; int ans,a1,a2; vector<int> v1,v2; int cnt[1<<20]; pair<int, int> t[1<<20]; int toadd[1<<20]; pair<int, int> combine(pair<int, int> p1,pair<int, int> p2) { if (p1.first!=p2.first) { if (p1.first>p2.first) return p1; return p2; } if (p1.second!=p2.second) { if (p1.second>p2.second) return p1; return p2; } return p1; } void build(int v,int tl,int tr) { if (tl==tr) { t[v]=make_pair(0,tl); return; } int tm=tl+tr; tm/=2; build(v*2,tl,tm); build(v*2+1,tm+1,tr); t[v]=combine(t[v*2],t[v*2+1]); } void push(int v,int tl,int tr) { t[v*2].first+=toadd[v]; t[v*2+1].first+=toadd[v]; toadd[v*2]+=toadd[v]; toadd[v*2+1]+=toadd[v]; toadd[v]=0; } void add(int v,int tl,int tr,int l,int r,int val) { if (l>r) return; if (tl==l&&tr==r) { t[v].first+=val; toadd[v]+=val; return; } push(v,tl,tr); int tm=tl+tr; tm/=2; add(v*2,tl,tm,l,min(r,tm),val); add(v*2+1,tm+1,tr,max(tm+1,l),r,val); t[v]=combine(t[v*2],t[v*2+1]); } pair<int, int> get(int v,int tl,int tr,int l,int r) { if (l>r) return make_pair(-1,-1); if (tl==l&&tr==r) return t[v]; int tm=tl+tr; tm/=2; push(v,tl,tr); pair<int, int> p1,p2; p1=get(v*2,tl,tm,l,min(r,tm)); p2=get(v*2+1,tm+1,tr,max(tm+1,l),r); return combine(p1,p2); } int get_leftmost(pair<int, int> p) { int l,r; l=0; r=v2.size()-1; if (ar[v2.back()]>p.second) return v2.size(); while (l<r) { int mid=l+r; mid/=2; if (ar[v2[mid]]>p.second) l=mid+1; else r=mid; } return l; } int get_rightmost(pair<int, int> p) { int l,r; l=0; r=v2.size()-1; while (l<r) { int mid=l+r+1; mid/=2; if (v2[mid]<p.first) r=mid-1; else l=mid; } return l; } void add_point(pair<int, int> p1) { // cout<<"add : "<<p1.first<<" "<<p1.second<<endl; int L=get_leftmost(p1); int R=get_rightmost(p1); add(1,0,v2.size()-1,L,R,1); } void remove_point(pair<int, int> p1) { // cout<<"remove: "<<p1.first<<" "<<p1.second<<endl; int L=get_leftmost(p1); int R=get_rightmost(p1); add(1,0,v2.size()-1,L,R,-1); } pair<int, int> solve() { int bst=0; int bp; return t[1]; /* for (int i=0;i<v2.size();i++) { if (cnt[i]>=bst) { bst=cnt[i]; bp=i; } } return make_pair(bst,bp);*/ } void show(set<pair<int, int> > S) { set<pair<int, int> > ::iterator it; for (it=S.begin();it!=S.end();it++) { pair<int, int> P=(*it); cout<<P.first<<" # "<<P.second<<endl; } cout<<"!"<<endl; } int main(){ //freopen("beavers.in","r",stdin); //freopen("beavers.out","w",stdout); //freopen("F:/in.txt","r",stdin); //freopen("F:/output.txt","w",stdout); ios_base::sync_with_stdio(0); //cin.tie(0); cin>>n; for (int i=1;i<=n;i++) { cin>>ar[i]; by_X.insert(make_pair(i,ar[i])); by_Y.insert(make_pair(ar[i],i)); } int mx=0; for (int i=1;i<=n;i++) { if (ar[i]>mx) { mx=ar[i]; v1.push_back(i); } } mx=1e9; for (int i=n;i;--i) { if (ar[i]<mx) { mx=ar[i]; v2.push_back(i); } } build(1,0,v2.size()-1); prev=make_pair(0,0); for (int i=0;i<v1.size();i++) { // cout<<"#"<<v1[i]<<endl; // show(by_X); // show(by_Y); for (;;) // remove left { it=by_X.begin(); pair<int, int> P=(*it); // cout<<"!"<<P.first<<" "<<P.second<<endl; if (P.first==v1[i]) // reached next corner break; by_X.erase(it); if (P.second<=prev.second) { remove_point(P); } } // cout<<"!"<<endl; for (;;) { it=by_Y.begin(); pair<int, int> P=(*it);// y-x swap(P.first,P.second);// x-y // cout<<"!!!"<<P.first<<" "<<P.second<<endl; if (P.first>=v1[i]) { add_point(P); } by_Y.erase(it);// first erase, then check if (P.second==ar[v1[i]]) break; } pair<int, int> tres=solve(); // cout<<"!!!"<<tres.first<<" "<<tres.second<<endl; if (tres.first>ans) { ans=tres.first; a1=v1[i]; a2=v2[tres.second]; } prev=make_pair(v1[i],ar[v1[i]]); } if (ans<=1) { cout<<"Cool Array"<<endl; } else { cout<<a1<<" "<<a2<<endl; } //cin.get();cin.get(); return 0;}