14097 - 平均数

给定一个长度为 n 的整数数列 a_1, a_2, \dots, a_n ,请你找出一个长度至少为 m 的连续子串(子数组),使得该子串中所有数的平均数最大。输出这个最大平均数的 1000 倍,直接舍去小数部分(即向下取整),不要四舍五入。

输入

第一行包含两个整数 n m ,用空格隔开。
接下来 n 行,每行一个整数 a_i ,表示数列中的第 i 个数。

输出

输出一个整数,表示最大平均数的 1000 倍向下取整后的结果。

样例

输入

10 6
6
4
2
10
3
8
5
9
4
1

输出

6500

提示

样例说明

该数列的一个长度至少为 6 的子串可以是 6 4 2 10 3 8,平均数为 ( (6+4+2+10+3+8)/6 = 33/6 = 5.5 ),1000 倍为 5500,但这不是最大的。实际上,子串 10 3 8 5 9 4 的平均数为 ( (10+3+8+5+9+4)/6 = 39/6 = 6.5 ),1000 倍为 6500。没有更大的平均数,因此输出 6500。

数据范围与约定

  • 1 \le m \le n \le 10^5
  • 0 \le a_i \le 2000
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题