Skyscrapers#5731
In a seaside village, there is an avenue of skyscrapers. Each skyscraper is m wide and has certain height. Due to very high price of parcels, any two consecutive skyscrapers are adjacent. The avenue lies close to the beach so the street is exactly at the sea level.
Unfortunately, this year, due to the global warming, the sea level started to increase by one meter each day. If the skyscraper height is no greater than the current sea level, it is considered flooded.
A region is a maximal set of non-flooded, adjacent skyscrapers. This term is of particular importance, as it is sufficient to deliver goods (like current, carrots or cabbages) to any single skyscraper in each region. Hence, the city mayor wants to know how many regions there will be in the hard days that come.
An example of an avenue with skyscrapers after days is given below.
The input contains several test cases. The first line contains an integer (t \le 15) denoting the number of test cases. Then test cases follow. Each of them begins with a line containing two numbers and (1 \le n, d \le 10^6), is the number of skyscrapers and is the number of days which the mayor wants to query. Skyscrapers are numbered from left to right. The next line contains integers h_1, h_2, ..., h_n where 1 \le h_{i} \le 10^9 is the height of skyscraper . The third line of a single test case contains numbers t_j such that 0 \le t_1 < t_2 < ... < t_{d-1} < t_{d} \le 10^9.
For each test case output numbers r_1, r_2, ..., r_d, where r_j is the number of regions on day t_j.
Example 1