Rabbit Carrot

#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int longest_nondec_subseq(const vector<int> &seq) {
	vector<int> min_endings;
	for (int i : seq) {
		/*
		 * notemos que usamos upper_bound en lugar de
		 * lower_bound porque solo tiene que ser no decreciente
		 */
		int pos = std::upper_bound(min_endings.begin(), min_endings.end(), i) -
		          min_endings.begin();
		// protocolo estándar de LIS
		if (pos == min_endings.size()) {
			min_endings.push_back(i);
		} else {
			min_endings[pos] = i;
		}
	}
	return min_endings.size();
}
 
int main() {
	int pole_num;
	int jump_height;
	std::cin >> pole_num >> jump_height;
	vector<int> poles(pole_num);
	for (int p = 0; p < pole_num; p++) { std::cin >> poles[p]; }
 
	vector<int> poss_unchanged;
	for (int i = 1; i <= pole_num; i++) {
		// solo agregamos si hay alguna esperanza de que quede sin cambiar
		if (i * jump_height >= poles[i - 1]) {
			poss_unchanged.push_back(i * jump_height - poles[i - 1]);
		}
	}
	cout << pole_num - longest_nondec_subseq(poss_unchanged) << endl;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class triusis {  // any other name breaks the grader lmao
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int poleNum = Integer.parseInt(initial.nextToken());
		int jumpHeight = Integer.parseInt(initial.nextToken());
 
		ArrayList<Integer> possUnchanged = new ArrayList<>();
		for (int p = 0; p < poleNum; p++) {
			int pole = Integer.parseInt(read.readLine());
			// solo agregamos si hay alguna esperanza de que quede sin cambiar
			if ((p + 1) * jumpHeight >= pole) {
				possUnchanged.add((p + 1) * jumpHeight - pole);
			}
		}
		System.out.println(poleNum - longestNondecSubseq(possUnchanged));
	}
 
	private static int longestNondecSubseq(ArrayList<Integer> arr) {
		ArrayList<Integer> minEndings = new ArrayList<>();
		for (int i : arr) {
			// hallamos el último lugar donde podemos insertarlo (porque solo tiene que ser
			// no decreciente)
			int pos = bisectRight(minEndings, i);
			// protocolo estándar de LIS
			if (pos == minEndings.size()) {
				minEndings.add(i);
			} else {
				minEndings.set(pos, i);
			}
		}
		return minEndings.size();
	}
 
	private static int bisectRight(ArrayList<Integer> arr, int x) {
		int lo = 0;
		int hi = arr.size();
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			if (x < arr.get(mid)) {
				hi = mid;
			} else {
				lo = mid + 1;
			}
		}
		return lo;
	}
}

from typing import List
from bisect import bisect_right
 
 
def longest_nondec_subseq(arr: List[int]) -> int:
	min_endings = []
	for i in arr:
		# bisect_right no left porque solo tiene que ser no decreciente
		pos = bisect_right(min_endings, i)
		# protocolo estándar de LIS
		if pos == len(min_endings):
			min_endings.append(i)
		else:
			min_endings[pos] = i
	return len(min_endings)
 
 
pole_num, jump_height = [int(i) for i in input().split()]
poles = [int(input()) for _ in range(pole_num)]
 
poss_unchanged = []
for i, p in enumerate(poles):
	if (i + 1) * jump_height >= p:
		poss_unchanged.append((i + 1) * jump_height - p)
 
print(pole_num - longest_nondec_subseq(poss_unchanged))