#3575. [USACO13MAR] Breed Proximity B

[USACO13MAR] Breed Proximity B

P3085 [USACO13OPEN] Breed Proximity G

题目描述

农夫约翰的N头奶牛(1 ≤ N ≤ 50,000)排成一列,每头奶牛都有一个整数品种ID。

相同品种的奶牛如果站得太近可能会发生争执。具体来说,如果两头相同品种奶牛的位置差不超过K(1 ≤ K < N),则称它们为"拥挤对"。

请计算所有拥挤对中最大的品种ID。如果没有拥挤对存在,则输出-1。

输入格式

第一行:两个空格分隔的整数N和K

接下来N行:每行包含一头奶牛的品种ID(0 ≤ ID ≤ 1,000,000)

输出格式

一个整数,表示拥挤对中的最大品种ID,若无拥挤对则输出-1

输入输出样例

输入 #1

6 3
7
3
4
2
3
4

输出 #1

4

样例解释

6头奶牛的品种ID依次为:7、3、4、2、3、4

拥挤对有:

  • 品种3的奶牛(位置2和5,差值为3)
  • 品种4的奶牛(位置3和6,差值为3)

其中最大的品种ID是4