Fshl0

Beautiful Sequence

Sep 10th, 2021
796
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1e5 + 9;
  6. const int INF = 1e17 + 9;
  7.  
  8. int A[N];
  9.  
  10. void solve () {
  11.     int n;
  12.     cin >> n;
  13.    
  14.     for (int i = 1; i <= n; ++i) {
  15.         cin >> A[i];
  16.         A[i] -= i;
  17.     }
  18.    
  19.     vector <int> dp (n + 1, INF);
  20.     dp[0] = -INF;
  21.    
  22.     for (int i = 1; i <= n; i++) {
  23.         if (A[i] < 0)
  24.             continue;
  25.        
  26.         int j = upper_bound (dp.begin(), dp.end(), A[i]) - dp.begin();
  27.         if (dp[j - 1] <= A[i] && A[i] < dp[j])
  28.             dp[j] = A[i];
  29.     }
  30.    
  31.     int len = 0;
  32.     for (int i = 1; i <= n; i++) {
  33.         if (dp[i] < INF)
  34.             len = i;
  35.     }
  36.    
  37.     cout << n - len << "\n";
  38.     return;
  39. }
  40.  
  41. int main () {
  42.     int t;
  43.     cin >> t;
  44.    
  45.     while (t--)
  46.         solve ();
  47.    
  48.     return 0;
  49. }
  50.  
RAW Paste Data