#include<bits/stdc++.h>
using namespace std;
char in[100], out[100];
int B[100100], A[100100];
int main(){
	for(int I=1;I<=20;I++){
		int n, d, i;
		sprintf(in,".%d.in",I);
		freopen(in,"w",stdout);
		//scanf("%d %d", &n, &d);
		if(I<10) n = I *10;
		else n = 100000;
		d = rand() % min(100, n); 
		printf("%lld %lld\n", n, d);
		for(i=1;i<=n;i++){
			if(i==1 or i==n) A[i] = 0;
			//scanf("%d", A+i);
			else A[i] = rand()%100+1;
			printf("%d",A[i]);
			if(i==n) printf("\n");
			else printf(" ");
		} 
		priority_queue <pair<int, int> > pq;
		pq.push({-1,1});
		A[1] = 1;
		for(i=2;i<=n;i++){
			while(!pq.empty() and i - pq.top().second-1 > d){
				pq.pop();
			}
			auto kk = pq.top();
			pq.push({kk.first-A[i]-1,i});
			B[i] = -(kk.first-A[i]-1);
		}
		sprintf(in,".%d.out",I);
		freopen(in,"w",stdout);
		printf("%d", B[n]);
	}
}