fork download
copy 
  1. // To understand what is happening in this file, please go to the end of the file.
  2.  
  3. #include "bits/stdc++.h"
  4.  
  5. #define int long long
  6. #define vi vector< int >
  7. #define fastIO() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  8. #define all(x) x.begin(),x.end()
  9. #define endl '\n'
  10.  
  11. using namespace std;
  12.  
  13. /*
  14.  
  15.  
  16.   ▄████  ██▓     ██▓▄▄▄█████▓ ▄████▄   ██░ ██
  17.  ██▒ ▀█▒▓██▒    ▓██▒▓  ██▒ ▓▒▒██▀ ▀█  ▓██░ ██▒
  18. ▒██░▄▄▄░▒██░    ▒██▒▒ ▓██░ ▒░▒▓█    ▄ ▒██▀▀██░
  19. ░▓█  ██▓▒██░    ░██░░ ▓██▓ ░ ▒▓▓▄ ▄██▒░▓█ ░██
  20. ░▒▓███▀▒░██████▒░██░  ▒██▒ ░ ▒ ▓███▀ ░░▓█▒░██▓
  21.  ░▒   ▒ ░ ▒░▓  ░░▓    ▒ ░░   ░ ░▒ ▒  ░ ▒ ░░▒░▒
  22.   ░   ░ ░ ░ ▒  ░ ▒ ░    ░      ░  ▒    ▒ ░▒░ ░
  23. ░ ░   ░   ░ ░    ▒ ░  ░      ░         ░  ░░ ░
  24.       ░     ░  ░ ░           ░ ░       ░  ░  ░
  25.  
  26. */
  27.  
  28. template<typename typC> istream &operator>>(istream &cin,vector<typC> &a) { for (auto &x:a) cin>>x; return cin; }
  29. template<typename typC> ostream &operator<<(ostream &cout,const vector<typC> &a) { int n=a.size(); if (!n) return cout; cout<<a[0]; for (int i=1; i<n; i++) cout<<' '<<a[i]; return cout; }
  30.  
  31.  
  32.  
  33. void itIsADream(){
  34.     int n; cin >> n;
  35.     vi a(n+1), first(n+1, -1), last(n+1, -1);
  36.     for(int i = 1; i <= n; i++) {
  37.         cin >> a[i];
  38.         if(first[a[i]] == -1) first[a[i]] = i;
  39.         last[a[i]] = i;
  40.     }
  41.     vi val;
  42.     for(int i = 1; i <= n; i++)
  43.         if(first[i] != -1)
  44.             val.push_back(i);
  45.     int ans = 1, cur = 1;
  46.     for(int i = 1; i < val.size(); i++) {
  47.         if(last[val[i-1]] < first[val[i]])
  48.             cur++;
  49.         else
  50.             cur = 1;
  51.         ans = max(ans, cur);
  52.     }
  53.     cout << val.size() - ans << "\n";
  54. }
  55.  
  56. int32_t main()
  57. {
  58.     fastIO();
  59.     // freopen("input.txt", "r", stdin);
  60.     // freopen("output.txt", "w", stdout);
  61.     int t = 1;
  62.     cin >> t;
  63.     while (t--)
  64.     {
  65.         itIsADream();
  66.     }
  67.     return 0;
  68. }
  69.  
  70. // to understand what is happening in this file, please go to the starting of the file.
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
18446744073709551615
https://ideone.com/w7lM2u
language:
C++ (gcc 8.3)
created:
4 hours 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!