题目描述

给定一个整数数组$a$和一个整数$k$，$k$表示滑动窗口的大小。你需要找出每个滑动窗口中的最大值与最小值的差，并输出这些差的最大值。

输入描述

第一行输入两个数字$n,k(1\le k\le n\le 10^5)$，分别表示数组的长度和滑动窗口的大小。

第二行输入$n$个整数$a_1,a_2,...a_n(-10^4\le a_i\le 10^4)$，表示数组中的元素。

输出描述

输出一个整数，表示所有长度为$k$的滑动窗口中最大值与最小值差的最大值。

样例

输入

8 3
1 3 -1 -3 5 3 6 7

输出

8