Minimizing Tiresome Flight Legs in the Byteotian Line Forest

In the Byteotian Line Forest there are \( n \) trees in a row. A little bird, starting at the top of the first tree, wants to fly to the top of the last tree. However, because the bird is very small, it may not be able to fly directly all the way without resting.

When the bird is on tree number \( i \), it can, in a single flight leg, fly to any of the trees \( i+1, i+2, \dots, i+k \) (i.e. the bird’s stamina allows a maximum jump of \( k \) trees). After each flight leg the bird must rest.

A flight leg is defined as tiresome if it ends on a tree whose height is at least as high as the starting tree, i.e. if the height at the landing tree \( h_j \) satisfies \( h_j \ge h_i \). Otherwise, the flight leg is not tiresome.

The goal is to choose a sequence of trees to land on (starting at tree 1 and ending at tree \( n \)) such that the overall flight has the minimum number of tiresome legs. Note that different birds may have different values of \( k \) (representing their stamina), and you are asked to help all of them!

Input/Output Format Note: In each test case, you are given the number of trees and their heights, followed by multiple queries (each with a different \( k \) value). For each query, output the minimum number of tiresome legs required to go from the first tree to the last one.

inputFormat

The input consists of multiple lines:

• The first line contains two integers \( n \) and \( q \), where \( n \) (\( 2 \le n \le 10^5 \)) is the number of trees in a row and \( q \) is the number of queries.
• The second line contains \( n \) integers: \( h_1, h_2, \dots, h_n \), where \( h_i \) represents the height of the \( i^{th} \) tree.
• The following \( q \) lines each contain a single integer \( k \) (\( 1 \le k \le n-1 \)), indicating the maximum number of trees the bird can jump over in one flight leg.

You may assume that it is always possible to reach the last tree.

outputFormat

For each query, output a single integer on a new line: the minimum number of tiresome legs required to fly from the first tree to the last tree.

sample

5 3
5 3 4 2 1
1
2
3

1
0
0