import java.util.*;
public class BoxColoring {
public static int minimumColorsNeeded(List<Integer> boxes, int s) {
int n = boxes.size();
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
int min = boxes.get(i), max = boxes.get(i);
dp[i] = i + 1;
for (int j = i; j >= 0; j--) {
min = Math.min(min, boxes.get(j));
max = Math.max(max, boxes.get(j));
if (i - j + 1 > dp[i]) {
break;
}
if (max - min <= s) {
dp[i] = Math.min(dp[i], (j > 0 ? dp[j - 1] : 0) + 1);
}
}
}
return dp[n - 1];
}
public static void main(String[] args) {
List<Integer> boxes = new ArrayList<>(Arrays.asList(1, 3, 1, 2, 4, 2, 1));
int s = 2;
int result = minimumColorsNeeded(boxes, s);
System.out.println(result); // Output: 3
}
}