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

通过次数

7

提交次数

23

Time Limit : 1 秒
Memory Limit : 128 MB

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

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

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

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

Input

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

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

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

Output

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

Examples

Input

5
1 10 3 10 2
3 1

Output

3

Input

7
7 7 7 7 12 7 7
2 3

Output

12

Input

2
1000000000 1000000000
1 1

Output

1000000000

Hint

  • bloomDay.length == n

  • 1 <= n <= 10^5

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

  • 1 <= m <= 10^6

  • 1 <= k <= n