#define _CRT_SECURE_NO_WARNINGS #pragma comment(linker, "/stack:16777216") #include <string> #include <vector> #include <map> #include <list> #include <iterator> #include <set> #include <queue> #include <iostream> #include <sstream> #include <stack> #include <deque> #include <cmath> #include <memory.h> #include <cstdlib> #include <cstdio> #include <cctype> #include <algorithm> #include <utility> #include <time.h> using namespace std; #define FOR(i, a, b) for(int i=(a);i<(b);i++) #define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i) #define FILL(A,value) memset(A,value,sizeof(A)) #define ALL(V) V.begin(), V.end() #define SZ(V) (int)V.size() #define PB push_back #define MP make_pair #define Pi 3.14159265358979 typedef long long Int; typedef unsigned long long UInt; typedef vector<int> VI; typedef pair<int, int> PII; const int INF = 100000000; const int MAX = 500007; const int MAX2 = 7; const int BASE = 1000000007; const int MOD = 1000000007; const double eps = 1e-9; struct RMQ { int n; int T[MAX * 4]; int I[MAX * 4]; int P[MAX * 4]; RMQ(){} RMQ(int len) { n = len; FOR (i,0,n*4) T[i] = P[i] = 0; } void build(int i, int l, int r) { I[i] = l; if (l != r) { int m = (l+r)/2; build(i*2, l, m); build(i*2+1, m+1, r); } } void push(int i, int l, int r) { if (l != r) { int m = (l+r)/2; T[i*2] += P[i]; T[i*2+1] += P[i]; P[i*2] += P[i]; P[i*2+1] += P[i]; P[i] = 0; } } void add(int l, int r, int d, int i, int tl, int tr) { push(i, tl, tr); if (l == tl && r == tr) { P[i] += d; T[i] += d; } else { int m = (tl+tr)/2; if (r <= m) add(l, r, d, i*2, tl, m); else if (l > m) add(l, r, d, i*2+1, m+1, tr); else { add(l, m, d, i*2, tl, m); add(m+1, r, d, i*2+1, m+1, tr); } if (T[i*2] >= T[i*2+1]) { T[i] = T[i*2]; I[i] = I[i*2]; } else { T[i] = T[i*2+1]; I[i] = I[i*2+1]; } } } PII get(int l, int r, int i, int tl, int tr) { push(i, tl, tr); if (l == tl && r == tr) return MP(T[i], I[i]); int m = (tl+tr)/2; if (r <= m) return get(l, r, i*2, tl, m); if (l > m) return get(l, r, i*2+1, m+1, tr); PII a = get(l, m, i*2, tl, m); PII b = get(m+1, r, i*2+1, m+1, tr); if (a.first >= b.first) return a; return b; } }; int n; int A[MAX]; vector<int> QL; vector<int> QR; int I[MAX]; int U[MAX]; set<int> S; RMQ R; void add(int x) { int val = A[x]; S.insert(x); int l = lower_bound(ALL(QR), x) - QR.begin(); if (l != SZ(QR) && QR[l] == x) return; //cout << '+' << x << ' ' << val << ' ' << l << endl; int Min = l, Max = SZ(QR)-1; while (Min < Max) { int Mid = (Min+Max)/2; if (Min+1 == Max) ++ Mid; if (A[QR[Mid]] >= val) Max = Mid-1; else Min = Mid; } //cout << Min << ' ' << A[QR[Min]] << endl; //cout << l << ' ' << Min << endl; if (A[QR[Min]] < val) R.add(l, Min, 1, 1, 0, R.n-1); } void del(int x) { int val = A[x]; S.erase(S.find(x)); int l = lower_bound(ALL(QR), x) - QR.begin(); if (l != SZ(QR) && QR[l] == x) return; int Min = l, Max = SZ(QR)-1; while (Min < Max) { int Mid = (Min+Max)/2; if (Min+1 == Max) ++ Mid; if (A[QR[Mid]] >= val) Max = Mid-1; else Min = Mid; } if (A[QR[Min]] < val) R.add(l, Min, -1, 1, 0, R.n-1); } int main() { //freopen("in.txt", "r", stdin); //freopen("intersection.in", "r", stdin); //freopen("intersection.out", "w", stdout); scanf("%d", &n); //FOR (i,0,n) //A[i] = i; //random_shuffle(A, A+n); FOR (i,0,n) { scanf("%d", &A[i]); //A[i] = i; -- A[i]; I[A[i]] = i; } FOR (i,0,n) { if (QL.empty()) QL.PB(i); else { if (A[QL.back()] <= A[i]) QL.PB(i); } } RFOR (i,n,0) { if (QR.empty()) QR.PB(i); else { if (A[QR.back()] >= A[i]) QR.PB(i); } } reverse(ALL(QR)); /*FOR (i,0,SZ(QL)) cout << QL[i] << ' '; cout << endl; FOR (i,0,SZ(QR)) cout << QR[i] << ' '; cout << endl;*/ R = RMQ(SZ(QR)); R.build(1, 0, R.n-1); int pos = 0; int res = 0, resl, resr; FOR (i,0,SZ(QL)) { int cur = QL[i]; int vl = (i == 0 ? 0 : A[QL[i-1]]); int vr = A[QL[i]]-1; //cout << vl << '-' << vr << endl; FOR (j,vl,vr+1) { int x = I[j]; add(x); } while (!S.empty() && *S.begin() < cur) { del(*S.begin()); } //cout << i << endl; //for (set<int>::iterator it = S.begin(); it != S.end(); ++it) //cout << *it << ' '; //cout << endl; while (pos < SZ(QR) && QR[pos] <= cur) ++ pos; if (pos != SZ(QR)) { int l = pos; int Min = l, Max = SZ(QR)-1; while (Min < Max) { int Mid = (Min+Max)/2; if (Min+1 == Max) ++ Mid; if (A[QR[Mid]] >= A[cur]) Max = Mid-1; else Min = Mid; } //cout << pos << ' ' << Min << endl; if (A[QR[Min]] < A[cur]) { int r = Min; PII p = R.get(l, r, 1, 0, R.n-1); if (p.second <= SZ(QR) && A[QR[p.second]] < A[QL[i]]) { if (p.first*2+1 > res) { res = p.first * 2 + 1; resl = QL[i]; //cout << p.first << ' ' << p.second << endl; resr = QR[p.second]; } else if (p.first*2+1 == res) { if (MP(QL[i], QR[p.second]) < MP(resl, resr)) { resl = QL[i]; resr = QR[p.second]; } } } } } } if (res == 0) printf("Cool Array\n"); else { //cout << res << endl; printf("%d %d\n", resl+1, resr+1); } /* int res2 = 0; FOR (i,0,n) { FOR (j,i+1,n) { if (A[i] < A[j]) continue; int cnt = 0; FOR (k,i+1,j) if (A[k] > A[j] && A[k] < A[i]) ++ cnt; res2 = max(res2, cnt); } } cout << res2 << endl; */ return 0; }