1. #include <iostream>
2.  
3. USING namespace std;
4.  
5. INT A[1000001];
6. INT B[1000001];
7. INT  j, i, k, k2;
8. long long licznik;
9.  
10. void MERGE(INT p,INT q,INT r)
11. {
12.         FOR(INT i = p; i <= r; i++)
13.         {
14.                 B[i] = A[i];
15.         }
16.  
17.         INT i = p;
18.         INT j = q;
19.         INT k = p;
20.         INT l = p;
21.  
22.         while(i <= q - 1 && j <= r)
23.         {
24.                 while(B[l] + k2 >= B[j] && l <= q - 1)
25.                 {
26.                         l++;
27.                 }
28.                 IF(B[i] <= B[j])
29.                 {
30.                          A[k] = B[j];
31.                          k++;
32.                          j++;
33.                          licznik += (q - l);
34.  
35.                 }
36.                 ELSE
37.                 {
38.                           A[k] = B[i];
39.                           k++;
40.                           i++;
41.                 }
42.         }
43.  
44.         while(i <= q - 1){
45.                 A[k] = B[i];
46.                 k++;
47.                 i++;
48.         }
49.  
50.         while(j <= r){
51.                 A[k] = B[j];
52.                 k++;
53.                 j++;
54.         }
55. }
56.  
57. void mergesort(INT k,INT l)
58. {
59.     IF(k==l)
60.     {
61.         RETURN;
62.     }
63.  
64.     INT s;
65.     s=(k+l)/2;
66.     mergesort(k,s);
67.     mergesort(s+1,l);
68.     MERGE(k,s+1,l+1);
69.     RETURN;
70. }
71.  
72.  
73.  
74. INT main()
75. {
76.  
77.     INT zes,iloscrz,x,y;
78.  
79.     cin>>zes;
80.  
81.     FOR(INT k=zes; k>=1; k--)
82.     {
83.         licznik=0;
84.         cin>>iloscrz>>k2;
85.         x=0;
86.         y=iloscrz-1;
87.  
88.         FOR(INT i=0; i<iloscrz; i++)
89.         {
90.             cin>>A[i];
91.         }
92.  
93.         mergesort(x,y);
94.  
95.         FOR(INT m=0; m<iloscrz; m++)
96.         {
97.             cout<<A[m]<<" ";
98.         }
99.         cout<<endl;
100.         cout<<licznik<<endl;
101.     }
102.  
103.     RETURN 0;
104. }
105.