// karanaggarwal #include <bits/stdc++.h> #include <cstring> #include <queue> #include <stack> #include <iostream> #include <vector> #include <algorithm> #include <cstdio> #include <unordered_map> #include <unordered_set> #include <map> #include <set> using namespace std; #define TRACE #ifdef TRACE #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__) template <typename Arg1> void __f(const char* name, Arg1&& arg1){ cerr << name << " : " << arg1 << std::endl; } template <typename Arg1, typename... Args> void __f(const char* names, Arg1&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); } #else #define trace(...) #endif #define si(x) scanf("%d",&x) #define F first #define S second #define PB push_back #define MP make_pair typedef long long LL; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<PII> VPII; vector<int> S; vector<int> E; const int MAXN = 6*500001; pair<int, int> tree[MAXN]; int lazy[MAXN]; int N; class segtree{ public: void init(int n){ N=n+1; build_tree(1,0,N); } void inc(int i, int j){ //trace(i,j,"query"); if(j<i)return; update_tree(1,0,N,i,j,1); } void dec(int i, int j){ //trace(i,j,"query"); if(j<i)return; update_tree(1,0,N,i,j,-1); } pair<int,int> query(int i, int j){ //trace(i,j,"query"); if(j<i)return MP(0,0); return query_tree(1,0,N,i,j); } void build_tree(int node, int a, int b) { if(a > b) return; //trace(node,a,b); if(a == b) { tree[node] = MP(0,a); return; } build_tree(node*2, a, (a+b)/2); build_tree(node*2+1, 1+(a+b)/2, b); tree[node] = tree[node*2]; } void update_tree(int node, int a, int b, int i, int j, int value) { if(lazy[node] != 0) { tree[node].F += lazy[node]; if(a != b) { lazy[node*2] += lazy[node]; lazy[node*2+1] += lazy[node]; } lazy[node] = 0; } if(a > b || a > j || b < i) return; if(a >= i && b <= j) { tree[node].F += value; if(a != b) { lazy[node*2] += value; lazy[node*2+1] += value; } return; } update_tree(node*2, a, (a+b)/2, i, j, value); update_tree(1+node*2, 1+(a+b)/2, b, i, j, value); if(tree[node*2].F>=tree[node*2+1].F) tree[node]=tree[node*2]; else tree[node]=tree[node*2+1]; } 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(INT_MIN,-1); if(lazy[node] != 0) { tree[node].F += lazy[node]; if(a != b) { lazy[node*2] += lazy[node]; lazy[node*2+1] += lazy[node]; } lazy[node] = 0; } if(a >= i && b <= j) return tree[node]; PII q1 = query_tree(node*2, a, (a+b)/2, i, j); PII q2 = query_tree(1+node*2, 1+(a+b)/2, b, i, j); if(q1.F>q2.F)return q1; if(q1.F<q2.F)return q2; if(q1.S<q2.S)return q1; return q2; } }; int A[500005]; int P[500005]; int R[500005]; // R[x] = i, is the smallest i such that S[i] >= x. int L[500005]; // L[x] = i, smallest i such that A[S[i]]] >= x. int main() { int t; t = 1; while(t--) { S.clear(); E.clear(); int n; si(n); for(int i = 0; i<n; i++) { si(A[i]); A[i]--; P[A[i]] = i; } S.PB(0); for(int i = 1; i<n; i++) { if(A[i] > A[S[S.size() - 1]]) S.PB(i); } if(S.size() == n) { printf("Cool Array\n"); continue;} E.PB(n-1); for(int i = n-2; i>=0; i--) { if(A[i] < A[E[E.size() - 1]]) E.PB(i); } reverse(E.begin(), E.end()); segtree ST; ST.init(E.size()); int j = 0; int k = 0; for(int i = 0; i<E.size(); i++) { while(j<E[i]){R[j] = i;j++;} while(k<A[E[i]]){L[k] = i; k++;} } while(j<n){R[j] = E.size();j++;} while(k<n){L[k] = E.size();k++;} // for(auto c : S) trace(c,A[c]); // for(auto e : E) trace(e,A[e]); // for(int i = 0; i<n; i++)trace(i,L[i]); // for(int i = 0; i<n; i++)trace(i,R[i]); j = 0; int ans = 0; PII tp; for(int i = 0; i < S.size(); i++) { int i1 = S[i]; int j1 = A[i1]; if(i>0) { int x = A[S[i-1]]; for(int k = S[i-1] + 1; k < S[i]; k++) { if(A[k] < x) { ST.dec(R[k],E.size() - 1); ST.inc(L[A[k]], E.size()-1); } } } //trace(i1,j1); while(j<j1) { int x = P[j]; // (x,j) if(x > i1) { //trace(x,j,R[x],L[j]); ST.inc(R[x],E.size() - 1); ST.dec(L[j], E.size()-1); } j++; } PII cr = ST.query(R[i1] , E.size()-1); // trace(i,S[i], A[S[i]], cr.F, cr.S); if(cr.F > ans) { ans = cr.F; tp = MP(S[i],E[cr.S]); } } if(ans==0) { bool done = false; for(int i = 0; i<n-1 and done==false; i++) { if(i != A[i]) { tp.F = i; for(int j = i+1; j<n; j++) if(A[j]<A[i]){tp.S = j; done = true; break;} } } } cout<<tp.F +1<<" "<<tp.S + 1<<endl; } return 0; }