fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pii pair<int, int>
  5. #define ft first
  6. #define sd second
  7.  
  8. const int oo = 2e5 + 3;
  9.  
  10. int n, k;
  11. int a[oo];
  12.  
  13. pii update(int max1, int max2, int d) {
  14. if (max1 < d) {
  15. max2 = max1;
  16. max1 = d;
  17. } else if (d > max2) {
  18. max2 = d;
  19. }
  20.  
  21. return {max1, max2};
  22. }
  23.  
  24. void solve() {
  25. cin >> n >> k;
  26. for (int i = 1; i <= n; ++i) {
  27. cin >> a[i];
  28. }
  29.  
  30. int last_pos[n + 1];
  31. pii val[n + 1];
  32.  
  33. for (int i = 1; i <= n; i++) {
  34. last_pos[i] = 0;
  35. val[i] = {-oo, -oo};
  36. }
  37.  
  38. for (int i = 1; i <= n; i++) {
  39. int d = i - last_pos[a[i]] - 1;
  40. val[a[i]] = update(val[a[i]].ft, val[a[i]].sd, d);
  41.  
  42. last_pos[a[i]] = i;
  43. }
  44.  
  45. for (int i = 1; i <= k; i++) {
  46. int d = (n + 1) - last_pos[i] - 1;
  47. val[i] = update(val[i].ft, val[i].sd, d);
  48. }
  49.  
  50. int res = oo;
  51. for (int i = 1; i <= k; i++) {
  52. int new_val = val[i].ft / 2;
  53. new_val = max(new_val, val[i].sd);
  54.  
  55. res = min(res, new_val);
  56. }
  57.  
  58. cout << res << "\n";
  59. }
  60.  
  61. int main() {
  62.  
  63. int t;
  64. cin >> t;
  65. while (t--) {
  66. solve();
  67. }
  68.  
  69. return 0;
  70. }
Success #stdin #stdout 0s 488KB
stdin
5
5 2
1 1 2 1 1
7 3
1 2 3 3 3 2 1
6 6
1 2 3 4 5 6
8 4
1 2 3 4 2 3 1 4
3 1
1 1 1
stdout
0
1
2
2
0