시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 512 MB 162 30 27 32.927%

문제

정우가 살고있는 마을은 분지(주위가 산지로 둘러싸여 주변보다 낮은 지형)이다. 한가로이 낮잠을 즐기던 정우는 마을의 왼쪽으로부터 물이 흘러 들어오고 있는 것을 보았다!

정우가 일찍 발견한 덕에 주민들과 정우는 무사히 탈출했지만, 호기심 꾸러기 정우는 흘러들어온 물이 언제 처음으로 K덩이가 되는지 궁금해졌다. (위의 그림에서 물은 3덩이이다.)

호기심 많고 마을 사람들도 구한 멋진 정우이지만, 똑똑하지는 않기 때문에 여러분이 도와주도록 하자.

입력

첫째 줄에 마을의 가로 길이 N, 정우가 궁금해하는 K가 공백을 사이에 두고 주어진다.

둘째 줄에 마을의 생김새에 대한 정보가 주어진다. N개의 수 A1, A2, ... , AN-1, AN이 주어지는데, Aii번째 땅의 깊이이다.

문제 설명의 그림에 나와있는 마을은 N = 8, A = [3, 6, 4, 2, 4, 3, 5, 5]인 경우이다.

출력

첫째 줄에 물이 최초로 K덩이가 되는 순간 직전의 물의 양을 출력한다. (왜 직전인지는 예제 해설을 보자)

만약 그런 순간이 없다면 -1을 출력한다.

정답이 32비트 정수를 넘을 수 있으므로 유의하라.

제한

  • 3 ≤ N ≤ 100,000
  • 2 ≤ KN
  • 1 ≤ Ai ≤ 1,000,000

서브태스크 1 (30점)

이 서브태스크는 다음의 조건을 만족한다.

  • K = 2
  • 1 ≤ N ≤ 1,000  

서브태스크 2 (40점)

이 서브태스크는 다음의 조건을 만족한다.

  • 1 ≤ N ≤ 1,000  

서브태스크 3 (30점)

이 서브태스크는 추가 제한 조건이 없다.

예제 입력 1

3 2
3 1 4

예제 출력 1

2

물이 2.0000000001만큼 들어오는 순간 아래 그림과 같이 물이 두 덩이가 된다. 때문에 그 직전 순간인 2를 정답으로 출력한다.


 

예제 입력 2

3 3
3 1 4

예제 출력 2

-1

마을에 물이 꽉차는 순간까지 물이 3덩이가 되지 않는다.

예제 입력 3

8 3
3 6 4 2 4 3 5 5

예제 출력 3

8

채점

  • 예제는 채점하지 않는다.