JANE  Jane and Tarzan
Jane and Tarzan have got cellphones and now they want to be available all the time. They live in a long line of trees and they are available iff the absolute difference between the heights of the two trees which they are on is not greater than D.
Jane and Tarzan are moving by the following rules: each second both Jane and Tarzan (simultaneously) jump, from the tree which they are on, on one of the adjacent trees (the left or the right one). It is forbidden to stay on the same tree. Moreover, in the very beginning and after each second they have to be available.
The trees in the line are numbered from 1 to N, respectively. Jane is interested in the pairs of trees (J, T) – let's call them good pairs – for which it holds: if Jane begins on the Jth tree, and Tarzan on the Tth tree, they can swap their positions after some time (moving by the rules) – so that Tarzan ends on the Jth tree, and Jane on the Tth tree.
Have a look on the first test example. D = 0 means that the heights of the trees which Jane and Tarzan are on have to differ by at most 0 (therefore, have to be equal) all the time. Pair (1, 5) is a good pair since we can take 1234565 as Jane's route, and 5654321 as Tarzan's route – this results in Jane and Tarzan swapping their initial positions (and being available all the time).
Output all the good pairs (J, T) in which J < T.
Input
In the first line of input there are integers N (1 ≤ N ≤ 100 000) and D (0 ≤ D ≤ 10^{9}).
In the next N lines there are N natural numbers less than 10^{9} – heights of the trees in the line (from the 1st tree to the Nth tree).
Output
Output all the requested pairs in sorted order. We define a pair (A, B) to be smaller than the pair (C, D) iff (A < C) or (A = C and B < D).
In all of the test data, the number of these pairs will not exceed 100 000.
Example
Input: 6 0 2 1 2 3 2 1 Output: 1 3 1 5 2 6 3 5
Input: 5 10 10 20 10 5 10 Output: 1 2 1 3 1 4 2 3 2 5 3 4 3 5 4 5
hide comments
vikas:
20150628 20:33:51
hint : reverse approach for storing states 

Adrian Satja Kurdija:
20110619 10:54:09
@Afrizal: Because when they jump from 1 5 to 2 4, the difference is 205 > 10. 

Afrizal:
20110604 02:45:57
on 2nd test case, why pair 1 5 isn't mentioned as the output? 
Added by:  Stjepan Glavina 
Date:  20100221 
Time limit:  0.105s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  author: Adrian Satja Kurdija 