/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
正整数 N と、長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
A の空でない連続部分列であって、同じ値を複数個含むようなものが存在するか判定してください。存在するならばそのようなもののうち最も短いものの長さを求めてください。
制約
- 1\leq N\leq 2\times 10^5
- 1\leq A_i\leq 10^6 (1\leq i\leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
問題文中の条件を満たす連続部分列が存在しないならば -1 と出力せよ。存在するならば、そのようなもののうち最も短いものの長さを出力せよ。
入力例 1
5 3 9 5 3 1
出力例 1
4
(3,9,5,3) と (3,9,5,3,1) が条件を満たします。短いのは (3,9,5,3) で、その長さは 4 です。
入力例 2
4 2 5 3 1
出力例 2
-1
条件を満たす連続部分列は存在しません。
入力例 3
10 1 1 2 3 5 8 13 21 34 55
出力例 3
2
Score : 300 points
Problem Statement
You are given a positive integer N and an integer sequence A = (A_1,A_2,\dots,A_N) of length N.
Determine whether there exists a non-empty (contiguous) subarray of A that has a repeated value, occurring multiple times in A. If such a subarray exists, find the length of the shortest such subarray.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^6 \ (1 \leq i \leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
If there is no (contiguous) subarray satisfying the condition in the problem statement, print -1. Otherwise, print the length of the shortest such subarray.
Sample Input 1
5 3 9 5 3 1
Sample Output 1
4
(3,9,5,3) and (3,9,5,3,1) satisfy the condition. The shorter one is (3,9,5,3), which has length 4.
Sample Input 2
4 2 5 3 1
Sample Output 2
-1
There is no subarray that satisfies the condition.
Sample Input 3
10 1 1 2 3 5 8 13 21 34 55
Sample Output 3
2