#include <bits/stdc++.h> using namespace std; #define ll long long int #define mod 1000000007 #define test int t;scanf("%d", &t);while(t--) #define maxr 500001 #define minv -1000000000 vector<int> vec; pair<int,int> tree[maxr*10]; int lazy[maxr*10]={0}, a[maxr], ind[maxr]; map<int,int> pos, invpos; bool st[maxr]={0}, end1[maxr]={0}; set<int> s; priority_queue<int> pq; void update(int node, int a, int b, int i, int j, pair<int,int> value) { if(lazy[node] != 0) { // This node needs to be updated tree[node].first += lazy[node]; // Update it if(a != b) { lazy[node*2] += lazy[node]; // Mark child as lazy lazy[node*2+1] += lazy[node]; // Mark child as lazy } lazy[node] = 0; // Reset it } if(a > b || a > j || b < i) // Current segment is not within range [i, j] return; if(a >= i && b <= j) { // Segment is fully within range tree[node].first += value.first; if(a != b) { // Not leaf node lazy[node*2] += value.first; lazy[node*2+1] += value.first; } return; } update(node*2, a, (a+b)/2, i, j, value); // Updating left child update(1+node*2, 1+(a+b)/2, b, i, j, value); // Updating right child if(tree[node*2].first>tree[node*2+1].first) { tree[node]=tree[node*2]; } else if(tree[node*2].first<tree[node*2+1].first)tree[node]=tree[node*2+1]; else if(tree[node*2].second<tree[node*2+1].second)tree[node]=tree[node*2]; else tree[node]=tree[node*2+1]; //tree[node] = max(tree[node*2], tree[node*2+1]); // Updating root with max value } pair<int,int> query_tree(int node, int a, int b, int i, int j) { if(a > b || a > j || b < i) return make_pair(minv,0); // Out of range if(lazy[node] != 0) { // This node needs to be updated tree[node].first += lazy[node]; // Update it if(a != b) { lazy[node*2] += lazy[node]; // Mark child as lazy lazy[node*2+1] += lazy[node]; // Mark child as lazy } lazy[node] = 0; // Reset it } if(a >= i && b <= j) // Current segment is totally within range [i, j] return tree[node]; pair<int,int> q1 = query_tree(node*2, a, (a+b)/2, i, j); // Query left child pair<int,int> q2 = query_tree(1+node*2, 1+(a+b)/2, b, i, j); // Query right child pair<int,int> res; // Return final result if(q1.first<q2.first)res = q2; else if(q2.first<q1.first)res=q1; else if(q2.second<q1.second)res=q2; else res=q1; return res; } void build_tree(int node, int a, int b) { if(a > b) return; // Out of range if(a == b) { // Leaf node tree[node] = make_pair(minv,pos[vec[a]]); // Init value return; } build_tree(node*2, a, (a+b)/2); // Init left child build_tree(node*2+1, 1+(a+b)/2, b); // Init right child //tree[node] = max(tree[node*2], tree[node*2+1]); // Init root value if(tree[node*2].first>tree[node*2+1].first) { tree[node]=tree[node*2]; } else if(tree[node*2].first<tree[node*2+1].first)tree[node]=tree[node*2+1]; else if(tree[node*2].second<tree[node*2+1].second)tree[node]=tree[node*2]; else tree[node]=tree[node*2+1]; } int main() { int n; scanf("%d", &n); for(int i=0;i<n;i++)scanf("%d", &a[i]); vec.push_back(a[n-1]); end1[n-1]=1; for(int i=n-2;i>=0;i--) { if(a[i]<vec[vec.size()-1]) { vec.push_back(a[i]); end1[i]=1; } } for(int i=0;i<n;i++)pos[a[i]]=i; reverse(vec.begin(),vec.end()); int cur=vec.size()-1; ind[n-1]=cur; for(int i=n-2;i>=0;i--) { if(cur>0)if(a[i]==vec[cur-1])cur--; ind[i]=cur; } for(int i=0;i<vec.size();i++)invpos[vec[i]]=i; st[0]=1; int prev=a[0]; for(int i=1;i<n;i++) if(a[i]>prev) { st[i]=1; prev=a[i]; } /*for(int i=0;i<vec.size();i++)printf("%d ", vec[i]); printf("\n"); for(int i=0;i<n;i++)printf("%d ", st[i]); printf("\n"); for(int i=0;i<n;i++)printf("%d ", end[i]); printf("\n"); for(map<int,int>::iterator it=pos.begin();it!=pos.end();it++) printf("%d-%d ", it->first, it->second); printf("\n"); for(map<int,int>::iterator it=invpos.begin();it!=invpos.end();it++) printf("%d-%d ", it->first, it->second); for(int i=0;i<n;i++)printf("%d ", ind[i]); printf("\n");*/ //for(int i=0;i<maxr*10;i++)tree[i]=make_pair(minv,0); int size=vec.size(); build_tree(1,0,size-1); cur = size-1; update(1,0,size-1,cur,cur,make_pair((minv*-1)+pos[vec[cur]],pos[vec[cur]])); s.insert(vec[cur]); pq.push(vec[cur]); int ans=minv; pair<int,int> ansp; for(int i=n-2;i>=0;i--) { if(st[i]) { while(!pq.empty()) { if(pq.top()>a[i])update(1,0,size-1,ind[pos[pq.top()]],size-1,make_pair(-2,0)); else break; //printf("2-%d\n", query_tree(1,0,size-1,size-1,size-1)); //printf("%d\n", pq.top()); pq.pop(); } pair<int,int> q = query_tree(1,0,size-1,0,size-1); q.first-=i; //printf("%d %d %d %d\n", i, q.first, q.second, q.first-(((q.second-i)*2-1)-q.first)); /*if(ans<q.first-(((q.second-i)*2-1)-q.first)) { ans=q.first-(((q.second-i)*2-1)-q.first); ansp = make_pair(i,q.second); } else if(ans==q.first-(((q.second-i)*2-1)-q.first)) { if(i<ansp.first || (i==ansp.first&&q.second<ansp.second)) { ans=q.first-(((q.second-i)*2-1)-q.first); ansp = make_pair(i,q.second); } }*/ if(ans<q.first) { ans=q.first; ansp = make_pair(i,q.second); } else if(ans==q.first) { if(i<ansp.first || (i==ansp.first&&q.second<ansp.second)) ansp = make_pair(i,q.second); } //update(1,0,size-1,cur,size-1,-1); } if(end1[i]) { cur--; update(1,0,size-1,cur,cur,make_pair((minv*-1)+pos[vec[cur]],pos[vec[cur]])); if(cur+1<=size-1)update(1,0,size-1,cur+1,size-1,make_pair(-1,pos[vec[cur]])); s.insert(vec[cur]); pq.push(vec[cur]); continue; } set<int>::iterator it = s.lower_bound(a[i]); it--; pq.push(a[i]); update(1,0,size-1,cur,invpos[*it],make_pair(1,0)); if(invpos[*it]+1<=size-1) update(1,0,size-1,invpos[*it]+1,size-1,make_pair(-1,0)); } if(ans<=0)printf("Cool Array\n"); else printf("%d %d\n", ansp.first+1, ansp.second+1); return 0; }