#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <algorithm> #include <string> #include <cstdio> #include <string.h> #include <assert.h> #include <iostream> #include <vector> using namespace std; const int N = 5e5 + 5; typedef long long li; #define forn(i, n) for(int i = 0; i < int(n); i++) #define x first #define y second #define pb push_back #define mp make_pair #define all(a) (a).begin(), (a).end() #define sz(a) int((a).size()) typedef pair<int, int> pt; int a[N]; int f[N]; int n; inline void add(int pos){ for (int i = pos; i <= n; i |= (i + 1)){ f[i]++; } } inline int get(int pos){ int res = 0; for (int i = pos; i >= 0; i = (i & (i + 1)) - 1){ res += f[i]; } return res; } inline li inv(){ for (int i = 0; i < n; i++) f[i] = 0; li res = 0; for (int i = n - 1; i >= 0; i--){ res += get(a[i] - 1); add(a[i]); } return res; } pair<int, int> trial(){ li ans = inv(); li anst = 0; int x = -1; int y = -1; for (int i = 0; i < n; i++){ for (int j = i + 1; j < n; j++){ swap(a[i], a[j]); anst = inv(); if (anst < ans){ ans = anst; x = i; y = j; } swap(a[i], a[j]); } } return make_pair(x, y); } pair<int, int> clever(){ for (int i = 0; i < n; i++) f[i] = 0; li res = 0; int mx1 = -1; int mxi1 = -1; int ta; for (int i = n - 1; i >= 0; i--){ ta = get(a[i] - 1); if (ta >= mx1){ mx1 = ta; mxi1 = i; } res += ta; add(a[i]); } for (int i = 0; i < n; i++) f[i] = 0; int mx2 = -1; int mxi2 = -1; for (int i = 0; i < n; i++){ ta = get(n - 1) - get(a[i] - 1); if (ta > mx2){ mx2 = ta; mxi2 = i; } res += ta; add(a[i]); } if (mx1 <= 0 || mx2 <= 0) return make_pair(-1, -1); return make_pair(mxi1, mxi2); } vector<int> t[4 * N]; inline void merge(vector<int> &a, vector<int> &b, vector<int> &res) { res.clear(); int i = 0, j = 0, n = sz(a), m = sz(b); while(i < n || j < m) { if(j >= m || (i < n && a[i] < b[j])) { res.pb(a[i]); i++; } else { res.pb(b[j]); j++; } } return; } void build(int idx, int l, int r) { if(l == r) { t[idx] = vector<int> (1, a[l]); return; } int mid = (l + r) / 2; build(2 * idx + 1, l, mid); build(2 * idx + 2, mid + 1, r); merge(t[2 * idx + 1], t[2 * idx + 2], t[idx]); //forn(i, sz(t[2 * idx + 1])) t[idx].pb(t[2 * idx + 1][i]); //forn(i, sz(t[2 * idx + 2])) t[idx].pb(t[2 * idx + 2][i]); //sort(all(t[idx])); return; } int get(int idx, int l, int r, int L, int R, int val) { if(L > R) return 0; if(l == L && r == R) { int it = int(upper_bound(all(t[idx]), val) - t[idx].begin()); //int it1 = int(lower_bound(all(t[idx]), val) - t[idx].begin()); return sz(t[idx]) - it; } int mid = (l + r) / 2; int res = 0; if(L <= mid) res += get(2 * idx + 1, l, mid, L, min(R, mid), val); if(R > mid) res += get(2 * idx + 2, mid + 1, r, max(mid + 1, L), R, val); return res; } inline int get(int i, int j) { return get(0, 0, n - 1, i + 1, j - 1, a[i]) - get(0, 0, n - 1, i + 1, j - 1, a[j]) + (a[i] > a[j] ? -1 : 1); } int main(){ //freopen("input.txt", "rt", stdin); //freopen("output.txt", "wt", stdout); scanf("%d", &n); for (int i = 0; i < n; i++){ scanf("%d", &a[i]); a[i]--; } build(0, 0, n - 1); // assert(n <= 50000); //pt nans = trial(); //cout << nans.x + 1 << ' ' << nans.y + 1 << endl; pair<int, int> pp = clever(); int L = pp.x, R = pp.y; int anss = get(L, R); pt ans = mp(L, R); //cerr << "init L R anss == " << L << ' ' << R << ' ' << anss << endl; forn(i, R) { if(a[i] < a[R]) continue; int cur = get(i, R); //cerr << "i cur == " << i << ' ' << cur << endl; if(cur < anss || cur == anss && mp(i, R) < ans) { anss = cur; ans = mp(i, R); } } for(int i = L + 1; i < n; i++) { if(a[L] < a[i]) continue; int cur = get(L, i); if(cur < anss || cur == anss && mp(L, i) < ans) { anss = cur; ans = mp(L, i); } } if (ans.first == -1 && ans.second == -1){ printf("Cool Array"); } else { assert(ans.first < ans.second); printf("%d %d", ans.first + 1, ans.second + 1); } }