309656: CF1714B. Remove Prefix

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:5 Solved:0

Description

Remove Prefix

题意翻译

### 题目描述 Polycarp是由一些长度为n的a整数序列组成的(1≤ai≤n)。只有当序列由不同的数字(即不同的数字)组成时,它才能使Polycarp高兴。 为了使他的序列像这样,Polycarp将进行一些移动(可能为零)。 在一个动作中,他可以: **删除**序列的**第一个(最左侧)元素。** 例如,在一次移动中,序列[3,1,4,3],将产生由不同数字组成的序列[1,4.3]。 确定他需要移动的最小次数,以便在剩余序列中所有元素都不同。**换句话说,在删除序列中的所有值后,查找给定序列的最小前缀的长度**。 #### 输入格式 第一行输入t(1 $\le t \le 10^4$)——测试组数 每个测试输入两行 第一行输入n(1 $\le n \le 2·10^5$)——序列的长度 第二行输入长度为n的a数组$a_1,a_2,…,a_n$(1$ \le a_i \le n$)——序列内容 保证$n$不超过$2·10^5$. #### 输出格式 一行一个当前测试数据变成Polycarp高兴的序列所需的最小步数

题目描述

Polycarp was presented with some sequence of integers $ a $ of length $ n $ ( $ 1 \le a_i \le 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 \le t \le 10^4 $ ) — the number of test cases. Each test case consists of two lines. The first line contains an integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of the given sequence $ a $ . The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le n $ ) — elements of the given sequence $ a $ . It is guaranteed that the sum of $ n $ values over all test cases does not exceed $ 2 \cdot 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

说明

The following are the sequences that will remain after the removal of prefixes: - $ [1, 4, 3] $ ; - $ [1] $ ; - $ [1] $ ; - $ [6, 5, 4, 3, 2, 1] $ ; - $ [2, 1] $ . It is easy to see that all the remaining sequences contain only distinct elements. In each test case, the shortest matching prefix was removed.

Input

题意翻译

### 题目描述 Polycarp是由一些长度为n的a整数序列组成的(1≤ai≤n)。只有当序列由不同的数字(即不同的数字)组成时,它才能使Polycarp高兴。 为了使他的序列像这样,Polycarp将进行一些移动(可能为零)。 在一个动作中,他可以: **删除**序列的**第一个(最左侧)元素。** 例如,在一次移动中,序列[3,1,4,3],将产生由不同数字组成的序列[1,4.3]。 确定他需要移动的最小次数,以便在剩余序列中所有元素都不同。**换句话说,在删除序列中的所有值后,查找给定序列的最小前缀的长度**。 #### 输入格式 第一行输入t(1 $\le t \le 10^4$)——测试组数 每个测试输入两行 第一行输入n(1 $\le n \le 2·10^5$)——序列的长度 第二行输入长度为n的a数组$a_1,a_2,…,a_n$(1$ \le a_i \le n$)——序列内容 保证$n$不超过$2·10^5$. #### 输出格式 一行一个当前测试数据变成Polycarp高兴的序列所需的最小步数

Output

题目大意:
Polycarp得到了一个由n个整数组成的序列a(1≤ai≤n)。只有当序列由不同的数字组成时,他才会高兴。为了使他的序列满足这个条件,Polycarp将进行一些操作(可能为零)。

在一次操作中,他可以删除序列的第一个(最左侧)元素。

确定他需要操作的最小次数,以便在剩余序列中所有元素都不同。换句话说,在删除序列中的所有值后,查找给定序列的最小前缀的长度。

输入输出数据格式:
输入格式:
第一行输入t(1≤t≤10^4)——测试组数
每个测试输入两行:
第一行输入n(1≤n≤2·10^5)——序列的长度
第二行输入长度为n的a数组$a_1,a_2,…,a_n$(1≤ai≤n)——序列内容

输出格式:
对于每个测试案例,输出一行——从序列开始处删除的最小元素数量,以便所有剩余元素都是不同的。题目大意: Polycarp得到了一个由n个整数组成的序列a(1≤ai≤n)。只有当序列由不同的数字组成时,他才会高兴。为了使他的序列满足这个条件,Polycarp将进行一些操作(可能为零)。 在一次操作中,他可以删除序列的第一个(最左侧)元素。 确定他需要操作的最小次数,以便在剩余序列中所有元素都不同。换句话说,在删除序列中的所有值后,查找给定序列的最小前缀的长度。 输入输出数据格式: 输入格式: 第一行输入t(1≤t≤10^4)——测试组数 每个测试输入两行: 第一行输入n(1≤n≤2·10^5)——序列的长度 第二行输入长度为n的a数组$a_1,a_2,…,a_n$(1≤ai≤n)——序列内容 输出格式: 对于每个测试案例,输出一行——从序列开始处删除的最小元素数量,以便所有剩余元素都是不同的。

加入题单

上一题 下一题 算法标签: