I realised that each page can have at most one special problem, and that the minimum number of special problems is always 1 (chapter 1, page 1, problem 1).
So I got the bound: (1 <= answer <= total pages)
Or more generally: (1 <= answer <= total pages <= total problems)
Basically my algorithm loops over every page and checks if the page number lies within the problem number range of that page. Here's my Python solution:

N, K = map(int, raw_input().split())
T = map(int, raw_input().split())

cnt = 0 # special problems
i = 0   # chapter number
j = 1   # page number
m = 1   # problem number

while i < N:
    if m <= j and j <= min(m + K - 1, T[i]):
        cnt += 1
    j += 1
    m += K
    if m > T[i]: # next chapter
        i += 1
        m = 1
print cnt