An array of size n≤106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example: The array is [1,3,−1,−3,5,3,6,7] , and k is 3.
Window position
Minimum value
Maximum value
[1,3,−1,]−3,5,3,6,7
−1
3
1,[3,−1,−3,]5,3,6,7
−3
3
1,3,[−1,−3,5,]3,6,7
−3
5
1,3,−1,[−3,5,3,]6,7
−3
5
1,3,−1,−3,[5,3,6,]7
3
6
1,3,−1,−3,5,[3,6,7]
3
7
Your task is to determine the maximum and minimum values in the sliding window at each position.
Input
The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.
Output
There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.
Sample Input
8 3
1 3 -1 -3 5 3 6 7
Sample Output
-1 -3 -3 -3 3 3
3 3 5 5 6 7
Translation
有一个长为 n 的序列 a,以及一个大小为 k 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。
There is a sequence of integers. Your task is to find the longest subsequence that satisfies the following condition: the difference between the maximum element and the minimum element of the subsequence is no smaller than m and no larger than k.
Input
There are multiple test cases.
For each test case, the first line has three integers, n, m and k. n is the length of the sequence and is in the range [1,100000]. m and k are in the range [0,1000000]. The second line has n integers, which are all in the range [0,1000000].
Proceed to the end of file.
Output
For each test case, print the length of the subsequence on a single line.
The semester is finally over and the summer holiday is coming. However, as part of your university’s graduation requirement, you have to take part in some social service during the holiday. Eventually, you decided to join a volunteer group which will plant trees in a mountain.
To simplify the problem, let’s represent the mountain where trees are to be planted with an N×N grid. Let’s number the rows 1 to N from top to bottom, and number the columns 1 to N from left to right. The elevation of the cell in the i-th row and j-th column is denoted by aij. Your leader decides that trees should be planted in a rectangular area within the mountain and that the maximum difference in elevation among the cells in that rectangle should not exceed M. In other words, if the coordinates of the top-left and the bottom-right corners of the rectangle are (x1,y1) and (x2,y2), then the condition ∣aij−akl∣≤M must hold for x1≤i,k≤x2,$ \ y_1 $$\le $$j,l \le y_2$. Please help your leader calculate the maximum possible number of cells in such a rectangle so that he’ll know how many trees will be planted.
输入描述
The input contains multiple cases. The first line of the input contains a single integer T(1≤T≤1000), the number of cases.
For each case, the first line of the input contains two integers N(1≤N≤500) and M(0≤M≤105). The following N lines each contain N integers, where the j-th integer in the i-th line denotes aij(1≤aij≤105).
It is guaranteed that the sum of N3 over all cases does not exceed 2.5×108.
输出描述
For each case, print a single integer, the maximum number of cells in a valid rectangle.