Description

H 小姐是学校里名副其实的女神， 每天想给 H 小姐献殷勤的追求者总会从女生宿舍排队排到校门口。 作为 H 小姐最要好的朋友， 小 Z 总是会穿梭在队伍中为H 小姐物色最佳男友。 小 Z 知道 H 小姐很看重身高， 于是这天她研究起了这群追求者的身高来。
已知共有 \(N\) 位追求者排成一列， 编号为 \(1...N\)， 编号为 \(i\) 的追求者身高为\(h[i]\)。小 Z 从队伍的某处出发， 沿着编号递增的方向经过了 \(M\) 位追求者， 一边走一边打量着这 \(M\) 位追求者的身高， 默默记下最高身高以及最高身高的变化次数。例如， 若 \(M=5\)， 经过的 \(M\) 位男生的身高分别为 \(3, 1, 2, 5, 7\)， 则小 Z 先记住了身高为 \(3\) 的男生， 然后忽略了接下来两位更矮的男生， 再然后依次遇到并记住了身高更高的两位男生（也即 \(5\) 和 \(7\)）， 最终记住了 \(M\) 位男生中身高最高的那位（也即 \(7\)） ， 在这个过程中小 Z 记住的最高身高变化了 \(3\) 次。
现在， 你知道小 Z 记录的最高身高变化了多少次， 以及最终记住的最高身高是多少吗？

Format

Input

第一行为 \(N\) 和 \(M\)，表示队伍的长度以及小 Z 经过的男生数量。
接下来 \(N\) 个数字， 依次表示 \(N\) 位追求者的身高。

Output

输出共 \(N-M+1\) 行， 每行两个数字。
第 \(i\) 行的两个数字分别表示若小 Z 从男生 \(i\) 走到男生 \(i+M-1\) ,其记录的最高身高变化了多少次， 以及最终记住的最高身高是多少。

Sample

Input

5 5
3 1 2 5 7

Output

3 7

Limitation

对于 \(30\%\) 的数据， \(2≤m≤n≤10000\)；
对于 \(50\%\) 的数据， \(2≤m≤n≤100000\)；
对于 \(70\%\) 的数据， \(2≤m≤n≤1000000\)；
对于 \(100\%\) 的数据， \(2≤m≤n≤10000000\)， 且身高在 unsigned int 范围内。