#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; const int MAXN = 500005; int N, a[MAXN]; vector <int> tree[4 * MAXN]; void build(int i, int L, int R){ if(L == R){ tree[i].push_back(a[L]); return; } int mid = (L + R) / 2; build(2 * i, L, mid); build(2 * i + 1, mid + 1, R); merge(tree[2 * i].begin(), tree[2 * i].end(), tree[2 * i + 1].begin(), tree[2 * i + 1].end(), back_inserter(tree[i])); } int query(int i, int L, int R, int Left, int Right, int p, int q){ if((Left <= L) && (R <= Right)){ return upper_bound(tree[i].begin(), tree[i].end(), q) - lower_bound(tree[i].begin(), tree[i].end(), p); } if((Right < L) || (R < Left))return 0; int mid = (L + R) / 2; return query(2 * i, L, mid, Left, Right, p, q) + query(2 * i + 1, mid + 1, R, Left, Right, p, q); } int get(int i, int j){ return query(1, 0, N - 1, i + 1, j - 1, a[j], a[i]) + (a[i] > a[j]); } int tree_ind[4 * MAXN], tree2[4 * MAXN], flag[4 * MAXN]; void refresh(int i, int L, int R){ if((2 * i) < (4 * MAXN))flag[2 * i] += flag[i]; if((2 * i + 1) < (4 * MAXN))flag[2 * i + 1] += flag[i]; tree2[i] += flag[i]; flag[i] = 0; } void build2(int i, int L, int R){ if(L == R){ tree_ind[i] = L; return; } int mid = (L + R) / 2; build2(2 * i, L, mid); build2(2 * i + 1, mid + 1, R); tree_ind[i] = tree_ind[2 * i]; } void update(int i, int L, int R, int p, int q, int v){ refresh(i, L, R); if((p <= L) && (R <= q)){ flag[i] += v; refresh(i, L, R); return; } if((q < L) || (R < p))return; int mid = (L + R) / 2; update(2 * i, L, mid, p, q, v); update(2 * i + 1, mid + 1, R, p, q, v); if(tree2[2 * i] >= tree2[2 * i + 1]){ tree2[i] = tree2[2 * i]; tree_ind[i] = tree_ind[2 * i]; }else{ tree2[i] = tree2[2 * i + 1]; tree_ind[i] = tree_ind[2 * i + 1]; } } pair <int, int> query2(int i, int L, int R, int p, int q){ refresh(i, L, R); if((p <= L) && (R <= q))return make_pair(tree2[i], tree_ind[i]); if((q < L) || (R < p))return make_pair(-1, -1); int mid = (L + R) / 2; pair <int, int> m1 = query2(2 * i, L, mid, p, q); pair <int, int> m2 = query2(2 * i + 1, mid + 1, R, p, q); if(m1.first >= m2.first)return m1; else return m2; } vector <int> s; void add(int st, int v, int d){ int L = st, R = s.size(); while(L < R){ int mid = (L + R) / 2; if(v < a[s[mid]])R = mid; else L = mid + 1; } //cout << st << ',' << v << ',' << d << ' ' << L << endl; update(1, 0, N - 1, st, L - 1, d); } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ scanf("%d", &N); for(int i = 0; i < N; i++) scanf("%d", &a[i]); for(int i = N - 1; i >= 0; i--){ if(s.empty())s.push_back(i); else if(a[s.back()] > a[i])s.push_back(i); } reverse(s.begin(), s.end()); /*cout << "s: "; for(int i = 0; i < s.size(); i++) cout << a[s[i]] << ' '; cout << endl; */ build(1, 0, N - 1); build2(1, 0, N - 1); int st = 0; for(int i = 0; i < (N - 1); i++){ while(s[st] <= i)st++; //cout << i << ", " << s[st] << endl; add(st, a[i], 1); } //cout << query2(1, 0, N - 1, 0, s.size() - 1).first << ' ' << query2(1, 0, N - 1, 0, s.size() - 1).second << endl; int res = 0, p = -1, q = -1, si = 0; for(int i = 0; i < (N - 1); i++){ while(s[si] <= i)si++; add(si, a[i], -1); pair <int, int> cur = query2(1, 0, N - 1, si, s.size() - 1); //cout << i << ' ' << cur.first << ',' << cur.second << endl; int cur_res = get(i, s[cur.second]); if(cur_res > res){ res = cur_res, p = i, q = s[cur.second]; } } if(res == 0)printf("Cool Array\n"); else printf("%d %d\n", p + 1, q + 1); return 0; }