fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
  5. #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
  6. #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
  7.  
  8. void solve() {
  9.     int n; scanf("%d", &n); 
  10.     vector<int> a(n + 1), b(n + 1);
  11.     FOR(i, 1, n) {
  12.         scanf("%d", &a[i]); 
  13.         b[i] = a[i];
  14.     }
  15.  
  16.     int f[n + 1], l[n + 1];
  17.     FOR(i, 0, n) f[i] = l[i] = -1; 
  18.  
  19.     FOR(i, 1, n) {
  20.         if (f[a[i]] == -1) f[a[i]] = i; 
  21.         l[a[i]] = i;
  22.     }
  23.  
  24.     sort(b.begin() + 1, b.end());
  25.     b.erase(unique(b.begin() + 1, b.end()), b.end());
  26.     vector<int> dp(n + 1, 0);
  27.     dp[1] = 1;
  28.  
  29.     FOR(i, 1, n - 1) {
  30.         if (l[b[i]] < f[b[i + 1]]) dp[i + 1] = dp[i] + 1;
  31.     }
  32.  
  33.     int answer = 0; 
  34.     FOR(i, 1, n) answer = max(answer, dp[i]);
  35.  
  36.     printf("%d\n", (int)b.size() - answer - 1);
  37. }
  38.  
  39. int main() {
  40.     int t; scanf("%d", &t); 
  41.     while (t--) solve();
  42. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
3
7
3 1 6 6 3 1 1
8
1 1 4 4 4 7 8 8
7
4 2 5 2 6 2 7
stdout
copy 
2
0
2
https://ideone.com/zRqqKT
language:
C++14 (gcc 8.3)
created:
6 days 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!