품종 근접도

면접 대비

시간 제한1초메모리 제한128 MB

요약

N마리의 소가 각자의 품종 번호와 함께 일렬로 서 있을 때, 위치 차이가 K 이하인 같은 품종 두 마리가 존재하면 그 품종 번호 중 최댓값을 구하고, 없으면 -1을 출력한다.

난이도: 쉬움10점 중 2점
유형: 배열, 해시맵, 구현
정답자: 아직 제출이 없습니다

문제

농부 John의 소 $N$ 마리( $1 \le N \le 50000$ )가 한 줄로 서 있으며, 각 소는 정수 품종 번호로 구분됩니다.

같은 품종의 두 소는 서 있는 위치가 너무 가까우면 서로 다툴 위험이 있습니다. 구체적으로, 같은 품종인 두 소의 줄 안에서의 위치 차이가 $K$ ( $1 \le K < N$ ) 이하이면 두 소는 "혼잡한(crowded)" 상태라고 합니다.

혼잡한 소 쌍의 품종 번호 중 최댓값을 구하세요.

입력

첫째 줄: 공백으로 구분된 두 정수 $N$ 과 $K$ .
둘째 줄부터 $N$ 개의 줄: 각 줄에 줄 안에 있는 소 한 마리의 품종 번호가 주어집니다. 모든 품종 번호는 $0$ 이상 $1000000$ 이하의 정수입니다.

출력

첫째 줄: 혼잡한 소 쌍의 품종 번호 중 최댓값. 혼잡한 소 쌍이 하나도 없으면 $-1$ 을 출력합니다.

힌트

소 6마리가 품종 번호 $7, 3, 4, 2, 3, 4$ 순서로 서 있고 $K = 3$ 입니다. 위치 차이가 $3$ 이하인 같은 품종의 두 소는 혼잡합니다. 품종 번호 $3$ 인 두 소(위치 $2$ 와 $5$ , 차이 $3$ )가 혼잡하고, 품종 번호 $4$ 인 두 소(위치 $3$ 과 $6$ , 차이 $3$ )도 혼잡합니다. 따라서 답은 $4$ 입니다.

예제4

예제 1
입력
```
6 3
7
3
4
2
3
4
```
예상 출력
```
4
```
예제 2
입력
```
3 1
1
2
3
```
예상 출력
```
-1
```
예제 3
입력
```
2 1
1000000
1000000
```
예상 출력
```
1000000
```
예제 4
입력
```
4 1
100
3
3
100
```
예상 출력
```
3
```