Note: this is my solution and not the official solution from the editorial.

Imagine we have a magic function $$$f(L, R)$$$ that tells us how many solutions there are in the range $$$[L, R]$$$ if we only want to conquer the cities inside the range. Also, let's say that $$$len$$$ is the length of the range. Now, try to define that function recursively:

1. If $$$a[L] < len$$$ and $$$a[R] < len$$$, then $$$f(L, R) = 0$$$, because there is no possible way to conquer all of these cities, since getting from one end of the segment to the other end requires at least $$$len$$$ steps.
2. If $$$a[L] \geq len$$$ and $$$a[R] < len$$$: Then, $$$f(L, R) = f(L+1, R)$$$, because whatever "conquering plan" we find in the range $$$[L+1, R]$$$, we can simply extend the plan by conquering the city $$$L$$$ afterwards.
3. If $$$a[L] < len$$$ and $$$a[R] \geq len$$$: Similar to case 2, but now we have $$$f(L, R) = f(L, R-1)$$$.
4. If $$$a[L] \geq len$$$ and $$$a[R] \geq len$$$: First, calculate $$$f(L+1, R-1)$$$. Then, we have to check if $$$L$$$ and $$$R$$$ are valid solutions. Let's check for $$$L$$$ first. Since the range $$$[L, R]$$$ is a contiguous range, we would conquer city $$$L$$$ at time 1, then city $$$L+1$$$ at time 2, $$$L+2$$$ at time 3 and so on until conquering city $$$R$$$ at time $$$len$$$. It's pretty clear that the times at which we conquer are increasing by one from left to right. So, $$$L$$$ is a valid starting city if

and so on. Subtracting $L$ on both sides gives us:

etc. The right side remains constant. Now, we can calculate a new array

We can now say:

Checking that can be done by a minimum segment tree. Checking if R is a valid solution can be done in a very similar fashion.