#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <string.h> #include <time.h> using namespace std; typedef long long lld; struct StrangeIT { struct Element { int from, to; vector< int > arr; }; Element IT[1100002]; int lbeg, lend; bool Leaf(int ind) { return (ind>=lbeg); } bool Legit(int ind) { return (ind < 1100002); } void Merge(int ch1, int ch2, int fat) { IT[fat].from = IT[ch1].from; IT[fat].to = IT[ch2].to; IT[fat].arr.clear(); int ind1=0, ind2=0; while (ind1 < IT[ch1].arr.size() || ind2 < IT[ch2].arr.size()) { if (ind2 == IT[ch2].arr.size()) { IT[fat].arr.push_back( IT[ch1].arr[ind1++] ); } else if (ind1 == IT[ch1].arr.size()) { IT[fat].arr.push_back( IT[ch2].arr[ind2++] ); } else { if (IT[ch1].arr[ind1] < IT[ch2].arr[ind2]) { IT[fat].arr.push_back( IT[ch1].arr[ind1++] ); } else { IT[fat].arr.push_back( IT[ch2].arr[ind2++] ); } } } } void Init(int arr[], int n) { lbeg = 1; while (lbeg < n) { lbeg *= 2; } lend = lbeg+n-1; for (int i=lend+1; i<1100002; i++) { IT[i].from = IT[i].to = n; IT[i].arr.clear(); } for (int i=lbeg; i<=lend; i++) { IT[i].from = IT[i].to = i-lbeg+1; IT[i].arr.clear(); IT[i].arr.push_back( arr[i-lbeg+1] ); } for (int i=lbeg-1; i>=1; i--) { if (Legit(i*2)) Merge(i*2, i*2+1, i); } } int Count(int ind, int x, int y) /// Including { int bl, br, bmid, bres=-1; int from, to; bl = 0; br=IT[ind].arr.size(); br--; while (bl <= br) { bmid = (bl+br)/2; if (IT[ind].arr[bmid] >= x) { bres = bmid; br = bmid-1; } else { bl = bmid+1; } } from = bres; bl = 0; br=IT[ind].arr.size(); br--; bres = -1; while (bl <= br) { bmid = (bl+br)/2; if (IT[ind].arr[bmid] <= y) { bres = bmid; bl = bmid+1; } else { br = bmid-1; } } to = bres; if (from==-1 || to==-1) return 0; return (to-from+1); } int QRY(int ind, int from, int to, int x, int y) { if (IT[ind].from > to || from > IT[ind].to) return 0; if (from <= IT[ind].from && IT[ind].to <= to) { return Count(ind, x, y); } //if (Legit(ind)) return QRY(ind*2, from, to, x, y) + QRY(ind*2+1, from, to, x, y); } int GetCount(int from, int to, int x, int y) { return QRY(1, from, to, x, y); } } IntervalTree; const int tlm1=1300*CLOCKS_PER_SEC/1000, tlm2 = 1500*CLOCKS_PER_SEC/1000, tlm3=1950*CLOCKS_PER_SEC/1000; bool RunForest() { return (clock() > tlm1); } bool ButReally_Run() { return (clock() > tlm2); } bool RUNMOTHAFUCKA() { return (clock() > tlm3); } int n, arr[500002]; void Input() { scanf("%d", &n); for (int i=1; i<=n; i++) { scanf("%d", &arr[i]); } } int temp[500002], touse[500002]; int CNTI(int from, int to) { if (from >= to) return 0; int mid = (from+to)/2; int ret = CNTI(from, mid)+CNTI(mid+1, to); int i1=from, i2=mid+1, tow=from; while (i1<=mid || i2<=to) { if (i2>to) { temp[tow++] = touse[i1++]; ret += i2-mid-1; } else if (i1>mid) { temp[tow++] = touse[i2++]; } else { if (touse[i1] < touse[i2]) { temp[tow++] = touse[i1++]; ret += i2-mid-1; } else { temp[tow++] = touse[i2++]; } } } for (int i=from; i<=to; i++) { touse[i] = temp[i]; } return ret; } int CountInversions() { for (int i=1; i<=n; i++) { touse[i] = arr[i]; } return CNTI(1, n); } pair< lld, pair<int, int> >ans; lld allInv; vector<int> begstart[500002]; void TryFastSwapping(int i1, int i2) { lld torem=0; torem = IntervalTree.GetCount(i1+1, n, arr[i2], arr[i1]-1); torem -= IntervalTree.GetCount(1, i1-1, arr[i2]+1, arr[i1]-1); torem += IntervalTree.GetCount(1, i2-1, arr[i2]+1, arr[i1]-1); torem -= IntervalTree.GetCount(i2+1, n, arr[i2]+1, arr[i1]-1); ans = min(ans, make_pair(allInv-torem, make_pair(i1, i2))); } vector<int> toswap1, toswap2; lld Beautifulness(int ind) { return ((lld)arr[ind]*(lld)arr[ind]) / ind; } double Beautifulness2(int ind) { return (double)arr[ind]/(double)ind; } int Beautifulness3(int ind) { return arr[ind]; } bool SH1(int a, int b) { return (Beautifulness(a) > Beautifulness(b)); } bool SH2(int a, int b) { return (Beautifulness2(a) > Beautifulness2(b)); } bool SH3(int a, int b) { return (Beautifulness3(a) > Beautifulness3(b)); } int main () { //freopen("input.txt", "r", stdin); Input(); allInv = CountInversions(); IntervalTree.Init(arr, n); bool perfect = true; for (int i=1; i<=n; i++) { if (arr[i] != i) { perfect = false; break; } } if (perfect) { printf("Cool Array\n"); return 0; } ans.first=(lld)n*(lld)n; int curmax=0, curmin=n+1; for (int i=1; i<=n; i++) { if (curmax>arr[i]) continue; curmax=arr[i]; toswap1.push_back(i); } for (int i=n; i>=1; i--) { if (curmin<arr[i]) continue; curmin = arr[i]; toswap2.push_back(i); } //srand(22335577); //random_shuffle(toswap1.begin(), toswap1.end()); int toind = 0; bool gettinout=false; sort(toswap1.begin(), toswap1.end(), SH1); for (int i=0; i<toswap1.size(); i++) { toind = i; for (int j=0; j<toswap2.size(); j++) { if (toswap2[j] <= toswap1[i]) break; if (RunForest()) { gettinout = true; break; } TryFastSwapping(toswap1[i], toswap2[j]); } if (gettinout) break; } if (gettinout) { sort(toswap1.begin(), toswap1.end(), SH2); for (int i=0; i<toswap1.size(); i++) { int from=(toswap2.size()/2+(toswap2.size()/2+toswap2.size()-1)/2)/2, to=(toswap2.size()/2+toswap2.size()-1)/2; for (int j=from; j<=to; j++) { if (toswap2[j] <= toswap1[i]) break; if (ButReally_Run()) { gettinout = true; break; } TryFastSwapping(toswap1[i], toswap2[j]); } if (gettinout) break; } } if (gettinout && toind+1<toswap1.size()) { sort(toswap1.begin()+toind, toswap1.end(), SH3); for (int i=toind; i<toswap1.size(); i++) { toind = i; for (int j=0; j<toswap2.size(); j++) { if (toswap2[j] <= toswap1[i]) break; if (RUNMOTHAFUCKA()) { printf("%d %d\n", ans.second.first, ans.second.second); return 0; } TryFastSwapping(toswap1[i], toswap2[j]); } } } printf("%d %d\n", ans.second.first, ans.second.second); }