1267 - 制作 m 束花所需的最少天数

通过次数

7

提交次数

23

时间限制 : 1 秒
内存限制 : 128 MB

给你一个整数数组 bloomDay,以及两个整数 mk

现需要制作 m 束花。制作花束时,需要使用花园中 相邻的 k 朵花

花园中有 n 朵花,第 i 朵花会在 bloomDay[i] 时盛开,恰好 可以用于 一束 花中。

请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1

输入

第一行为1个整数n,表示花的数量

第二行为n个整数,表示每朵花的开花时间

第三行为2个整数m,k,表示需要使用连续的k朵花形成一个花束,共形成m个花束

输出

从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1

样例

输入

5
1 10 3 10 2
3 1

输出

3

输入

7
7 7 7 7 12 7 7
2 3

输出

12

输入

2
1000000000 1000000000
1 1

输出

1000000000

提示

  • bloomDay.length == n

  • 1 <= n <= 10^5

  • 1 <= bloomDay[i] <= 10^9

  • 1 <= m <= 10^6

  • 1 <= k <= n