Problem - 1714B - Codeforces
codeforces.com
- 제목
Remove Prefix
- 조건
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
- 문제
Polycarp was presented with some sequence of integers a of length n (1≤ai≤n). A sequence can make Polycarp happy only if it consists of different numbers (i.e. distinct numbers).
In order to make his sequence like this, Polycarp is going to make some (possibly zero) number of moves.
In one move, he can:
remove the first (leftmost) element of the sequence.
For example, in one move, the sequence [3,1,4,3] will produce the sequence [1,4,3], which consists of different numbers.
Determine the minimum number of moves he needs to make so that in the remaining sequence all elements are different.
In other words, find the length of the smallest prefix of the given sequence a, after removing which all values in the sequence will be unique.
- 입력
The first line of the input contains a single integer t (1≤t≤10^4) — the number of test cases.
Each test case consists of two lines.
The first line contains an integer n (1≤n≤2⋅10^5) — the length of the given sequence a.
The second line contains n integers a1,a2,…,an (1≤ai≤n) — elements of the given sequence a.
It is guaranteed that the sum of n values over all test cases does not exceed 2⋅10^5.
- 출력
For each test case print your answer on a separate line — the minimum number of elements that must be removed from the beginning of the sequence so that all remaining elements are different.
| 예제 입력 1 | 5 4 3 1 4 3 5 1 1 1 1 1 1 1 6 6 5 4 3 2 1 7 1 2 1 7 1 2 1 |
| 예제 출력 1 | 1 4 0 0 5 |
#include <iostream>
#include <algorithm>
using namespace std;
#define endl '\n'
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
bool isThere[200001];
int tc, sz;
cin >> tc;
while(tc--){
cin >> sz;
int *arr = new int[sz], ans = -1;
for(int n = 0 ; n < 200001 ; n++) isThere[n] = false;
for(int n = 0 ; n < sz; n++) cin >> arr[n];
for(int n = sz - 1 ; n >= 0 ; n--){
if(!isThere[arr[n]]) isThere[arr[n]] = true;
else{
ans = n;
break;
}
}
cout << ans + 1 << endl;
}
return 0;
}