fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5. int testcase, n;
  6. long long a[100005];
  7.  
  8.  
  9. int main()
  10. {
  11.     ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
  12.     cin >> testcase;
  13.     a[0] = -1e18 - 1;
  14.     while(testcase--) {
  15.         cin >> n;
  16.         for(int i = 1; i <= n; ++i) cin >> a[i];
  17.         if(n == 1) {cout << 0 << '\n'; continue;}
  18.         int r = n;
  19.         for(int i = n - 1; i >= 2; --i) {
  20.             if(a[i] < a[i + 1]) --r;
  21.             else break;
  22.         }
  23.         long long res = n - r + 1;
  24.         for(int i = 1; i <= n - 1; ++i) {
  25.             if(a[i] <= a[i - 1]) break;
  26.             while(r < n + 1 && a[r] <= a[i]) ++r;
  27.             r = max(r, i + 2);
  28.             res += (n + 2 - r);
  29.         }
  30.         cout << res << '\n';
  31.  
  32.     }
  33.     return 0;
  34. }
  35.  
Success #stdin #stdout 0.01s 5420KB
comments (?)
stdin
copy 
3
1 1 2
4
2 4 3 5
stdout
copy 
0
2
3
https://ideone.com/0XJELz
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!