Broadcast Tower Offers

City X has $N$ buildings standing in one row from west to east. The westmost building is number 1 and the eastmost is number $N$. The heights are integers $h_1, h_2, \dots, h_N$, and no two buildings have the same height. The city government plans to build one broadcast tower in the same row. The tower can stand west of building 1, between two neighbouring buildings, or east of building $N$. Its height is $H$, and $H$ differs from every building height.

Because of an unusual design, the tower sends signals only to the west. A signal is a horizontal ray that travels parallel to the ground, and rays leave the whole body of the tower, from the top down to the bottom. The tower therefore emits a continuous band of rays whose width equals the height of the tower. A ray stops where it hits a building. Each building has a receiver on its roof, and a building receives the message if at least one ray reaches that receiver.

In other words, building $i$ receives the message exactly when all three conditions hold: building $i$ stands west of the tower, $h_i$ is not greater than the height of the tower, and no building $j$ with $j > i$ standing between building $i$ and the tower is higher than building $i$.

In the figure above the buildings that receive the message are 2, 5, 6, and 9.

Only one tower will be built, but the city government received $K$ offers of different heights. The offers are numbered from 1 to $K$. Every offered height differs from the other offered heights and from every building height. Before the decision is made, the city leaders want to know, for each offer, the largest number of buildings that receive the message. Each offer is measured on its own best position.

You are given the heights of the buildings and the heights of the offered towers. Write a program that prints, for each offer, the largest number of buildings that receive the message.

The first line contains the number of buildings $N$ and the number of offers $K$, separated by a space.

The second line contains the heights of the $N$ buildings, separated by spaces, in order from building 1 to building $N$.

The third line contains the heights of the $K$ offered towers, separated by spaces, in order from offer 1 to offer $K$.

Print $K$ integers on one line, separated by spaces. The $i$-th number is the largest number of buildings that receive the message when the tower of offer $i$ is built in its best position.

• $1 \le N \le 1000000$
• $1 \le K \le 100000$
• Every building height and every offered tower height is an integer between $1$ and $10^9$
• The building heights are pairwise different
• The offered heights are pairwise different, and none of them equals a building height

The pictures below show a best position for each offer in the example.

Position of tower 1. The buildings that receive the message are 10, 12, 13, 15, and 16.

Position of tower 2. The buildings that receive the message are 2, 3, 5, 6, 7, and 8.

Position of tower 3. The buildings that receive the message are 12, 13, 15, and 16.