import java.util.*;
import java.io.*;
public class triusis {
public static void main(String[] args) throws IOException {
Reader in = new Reader();
PrintWriter out = new PrintWriter(System.out);
int N = in.nextInt(), K = in.nextInt();
long[] arr = new long[N];
for (int i = 0; i < N; i++) {
int h = in.nextInt();
arr[i] = h - i * K;
}
TreeSet<Long> set = new TreeSet<>();
for (long i : arr) {
set.add(i);
}
HashMap<Long, Integer> map = new HashMap<>();
int index = 0;
for (long i : set) {
map.put(i, index++);
}
int[] arr2 = new int[N];
for (int i = 0; i < N; i++) {
arr2[i] = map.get(arr[i]);
}
int M = 1;
while (M < 200001) {
M <<= 1;
}
int[] tree = new int[M * 2];
for (int i = 0; i < N; i++) {
int l = arr2[i] + M, r = M * 2 - 1;
int max = 0;
while (l <= r) {
if (l % 2 == 1) {
max = Math.max(max, tree[l]);
l >>= 1;
l++;
} else {
l >>= 1;
}
if (r % 2 == 0) {
max = Math.max(max, tree[r]);
r >>= 1;
r--;
} else {
r >>= 1;
}
}
max++;
int current = arr2[i] + M;
while (current > 0) {
tree[current] = Math.max(tree[current], max);
current >>= 1;
}
}
out.println(N - tree[1]);
out.close();
}
static class Reader {
BufferedInputStream in;
public Reader() {
in = new BufferedInputStream(System.in);
}
public String nextLine() throws IOException {
int c;
StringBuilder sb = new StringBuilder("");
while ((c = in.read()) != '\n')
sb.append((char)(c));
return sb.toString();
}
public String next() throws IOException {
int c;
StringBuilder sb = new StringBuilder("");
while ((c = in.read()) != ' ' && c != '\n')
sb.append((char)(c));
return sb.toString();
}
public int nextInt() throws IOException {
return (int)nextLong();
}
public long nextLong() throws IOException {
int c;
long res = 0;
boolean start = false, negative = false;
while ((c = in.read()) != ' ' && c != '\n' || !start)
if (c >= '0' && c <= '9' || c == '-') {
start = true;
if (c == '-')
negative = true;
else
res = res * 10 + c - '0';
}
return res * (negative ? -1 : 1);
}
}
public static void sort(int[] arr) {
List<Integer> list = new ArrayList<>();
for (int i : arr) {
list.add(i);
}
Collections.sort(list);
for (int i = 0; i < arr.length; i++) {
arr[i] = list.get(i);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
10536 KB |
Output is correct |
| 2 |
Incorrect |
59 ms |
10248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
10536 KB |
Output is correct |
| 2 |
Incorrect |
59 ms |
10248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
10536 KB |
Output is correct |
| 2 |
Incorrect |
59 ms |
10248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
10536 KB |
Output is correct |
| 2 |
Incorrect |
59 ms |
10248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
