fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const int N = 500005;
  5. ll inter[N];
  6. int n, arr[N], _arr[N];
  7. int ls(int indx) {
  8. return indx & (-indx);
  9. }
  10. void update(int indx, int val) {
  11. for (; indx <= n; indx += ls(indx))
  12. inter[indx] += val;
  13. }
  14. ll get(int indx) {
  15. ll res = 0;
  16. for (; indx > 0; indx -= ls(indx))
  17. res += inter[indx];
  18. return res;
  19. }
  20. int main() {
  21. cin >> n;
  22. for (int i = 0; i < n; ++i)
  23. cin >> arr[i], _arr[i] = arr[i];
  24. int pos = -1;
  25. ll ans = 0, mx = 0;
  26. for (int i = n - 1; i >= 0; --i) {
  27. ll tmp = get(arr[i]);
  28. ans += tmp;
  29. update(arr[i], 1);
  30. if (tmp >= mx) {
  31. mx = tmp;
  32. pos = i;
  33. }
  34. }
  35. if (pos == -1) {
  36. cout << "Cool Array" << endl;
  37. return 0;
  38. }
  39. int x = pos;
  40. reverse(arr, arr + n);
  41. for (int i = 0; i < n; ++i)
  42. arr[i] = n - arr[i] + 1;
  43. ll _ans = 0, _mx = 0;
  44. pos = -1;
  45. ll cnt = 0;
  46. memset(inter, 0, sizeof(inter));
  47. for (int i = n - 1 - x; i >= 0; --i) {
  48.  
  49. ll tmp = get(arr[i])-cnt;
  50. update(arr[i], 1);
  51. if (tmp > _mx) {
  52. _mx = tmp;
  53. pos = i;
  54. }
  55. cnt+=arr[i] < arr[n-x-1];
  56. }
  57. if (pos == -1)
  58. cout << "Cool Array" << endl;
  59. else
  60. cout << x + 1 << " " << n - pos << endl;
  61. return 0;
  62. }
  63.  
Success #stdin #stdout 0s 11272KB
stdin
7
3 2 1 7 4 5 6
stdout
4 5