// spnauT // #include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int _b=(b),i=(a); i<_b; ++i) #define ROF(i,b,a) for(int _a=(a),i=(b); i>_a; --i) #define REP(n) for(int _n=(n); --_n>=0;) #define _1 first #define _2 second #define PB(x) push_back(x) #define SZ(x) int((x).size()) #define ALL(x) (x).begin(), (x).end() #define MSET(m,v) memset(m,v,sizeof(m)) #define MAX_PQ(T) priority_queue <T> #define MIN_PQ(T) priority_queue <T,vector<T>,greater<T>> #define IO() {ios_base::sync_with_stdio(0); cin.tie(0);} #define nl '\n' #define cint1(a) int a; cin>>a #define cint2(a,b) int a,b; cin>>a>>b #define cint3(a,b,c) int a,b,c; cin>>a>>b>>c typedef long long LL; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<LL> VL; typedef vector<PII> VP; template<class A, class B> inline bool mina(A &x, B y) {return(y<x)?(x=y,1):0;} template<class A, class B> inline bool maxa(A &x, B y) {return(x<y)?(x=y,1):0;} template<class A, class B> inline A geta(A &x, const B y) {A t=x;x=y;return t;} class LazySegmentTree { private: // (*) typedef PII value_t; typedef int lazy_t; typedef int qvalue_t; typedef PII qresult_t; int ready; VI l_b, r_b; // left/right bound (interval) int q_l, q_r; // query left/right (interval) int size, base; // ~2*|array|, ~|array|, both must be power of 2 vector <value_t> seg_value; vector <lazy_t> seg_lazy; qvalue_t query_value; qresult_t query_result; inline PII maxp(PII a, PII b) { if(a._1 > b._1 || (a._1 == b._1 && a._2 < b._2)) return a; else return b; } //(*) inline value_t def_value() {return PII(0,0);} inline lazy_t def_lazy() {return 0;} inline qresult_t def_qresult() {return PII(-1,0);} inline void accum_result(int id) { query_result = maxp(query_result, seg_value[id]); } inline void update_lazy_qvalue(int id) { seg_lazy[id] += query_value; } inline void update_value_from_lazy(int id) { seg_value[id]._1 += seg_lazy[id]; } inline void update_parent_value(int id, int lc, int rc) { seg_value[id] = maxp(seg_value[lc], seg_value[rc]); } inline void build_parent_value(int id, int lc, int rc) { update_parent_value(id,lc,rc); } inline void update_children_lazy(int id, int lc, int rc) { lazy_t lazy = seg_lazy[id]; seg_lazy[lc] += lazy; seg_lazy[rc] += lazy; } inline int l_ch(int id) {return id+id;} inline int r_ch(int id) {return id+id+1;} void seg_push(int id) { if(seg_lazy[id] == def_lazy()) return; update_value_from_lazy(id); if(id < base) update_children_lazy(id, l_ch(id), r_ch(id)); seg_lazy[id] = def_lazy(); } void seg_merge(int id) { if(id >= base) return; int lc = l_ch(id), rc = r_ch(id); if(!ready) build_parent_value(id,lc,rc); else {seg_push(lc); seg_push(rc); update_parent_value(id,lc,rc);} } void internal_update(int id) { if(q_r < l_b[id] || r_b[id] < q_l) return; if(q_l <= l_b[id] && r_b[id] <= q_r) {update_lazy_qvalue(id); seg_push(id); return;} seg_push(id); internal_update(l_ch(id)); internal_update(r_ch(id)); seg_merge(id); } void internal_query(int id) { if(q_r < l_b[id] || r_b[id] < q_l) return; if(q_l <= l_b[id] && r_b[id] <= q_r) {seg_push(id); accum_result(id); return;} seg_push(id); internal_query(l_ch(id)); internal_query(r_ch(id)); seg_merge(id); } void update_bound(int id, int l, int r) { l_b[id] = l; r_b[id] = r; if(l >= r) return; int m = (l+r) / 2; update_bound(l_ch(id), l, m); update_bound(r_ch(id), m+1, r); } public: LazySegmentTree() {init(vector <value_t> ());} LazySegmentTree(int n) {init(vector <value_t> (n, def_value()));} LazySegmentTree(const vector <value_t> &A) {init(A);} void init(const vector <value_t> &A) { ready = 0; int n = A.size(); if(n <= 0) {base = size = 0; return;} base = 2; while(base < n) base <<= 1; size = base * 2; // base >= 2, size >= 4, to avoid too small cases l_b.resize(size); r_b.resize(size); seg_value.resize(size, def_value()); seg_lazy.resize(size, def_lazy()); update_bound(1, 0, base-1); FOR(i,0,n) seg_value[i + base] = A[i]; ROF(i,base-1,0) seg_merge(i); ready = 1; } void update(int l, int r, const qvalue_t value) { assert(size > 0); if(l > r) return; q_l = l; q_r = r; query_value = value; internal_update(1); } qresult_t query(int l, int r) { query_result = def_qresult(); assert(size > 0); if(l <= r) {q_l = l; q_r = r; internal_query(1);} return query_result; } int leaves_count() const {return size - base;} }; #define MAXN (500005) int N; int A[MAXN]; int B[MAXN]; int C[MAXN]; int P[MAXN]; int bn, cn; LazySegmentTree L; void update(int a, int val) { int lo = 0; int hi = bn-1; int q = bn; while(lo <= hi) { int mid = (lo+hi)/2; if(P[B[mid]] > P[a]) { q = mid; hi = mid-1; } else lo = mid+1; } if(q < bn && B[q] < a) L.update(B[q], a-1, val); } PII query(int a) { return L.query(0,a); } int main() { IO(); cin >> N; int eq = 1; FOR(i,0,N) { cint1(a); --a; A[i] = a; P[A[i]] = i; eq &= i == a; } if(eq) { cout << "Cool Array" << nl; return 0; } VP L1(N); FOR(i,0,N) L1[i] = PII(0,i); L.init(L1); FOR(i,0,N) { while(bn > 0 && B[bn-1] > A[i]) --bn; B[bn++] = A[i]; } FOR(i,0,N) { int p = P[i]; while(cn > 0 && P[C[cn-1]] > p) --cn; C[cn++] = i; } MIN_PQ(int) Q; int sol = 0; PII sola; { int a = 0; while(a == A[a]) ++a; int b = N-1; while(b == A[b]) --b; sola = PII(a+1,b+1); } int j = 0; FOR(c,0,cn) { int a = C[c]; int p = P[a]; while(!Q.empty() && Q.top() < p) { int q = Q.top(); Q.pop(); update(A[q], -1); } while(j < a) { Q.push(P[j]); update(j++, 1); } ++j; PII res = query(a); if(maxa(sol, res._1)) sola = PII(p+1, P[res._2]+1); } cout << sola._1 << ' ' << sola._2 << nl; return 0; }