19670번 - Pilot 다국어

Rar the Cat has finally fulfilled his childhood dream of becoming a pilot, and wants to take his friend, Dinosaur, on a few scenic flights. Rar lives on a linear world, which can be described as a series of N integers, with the ith integer H_i indicating the height of the ith mountain from the leftmost edge of his world.

For example, the world described with N = 6, H = {1, 3, 2, 4, 1, 2} will look like this:

Rar has a total of Q planes that he wishes to show off, with the ith plane having a maximum cruising altitude of Y_i metres. Each flight starts from the sth mountain and ends on the eth mountain. We may assume that s ≤ e, i.e. Rar will always fly toward the right. As each of his planes have a maximum cruising altitude, he is unable to fly across, take off from, or land on a mountain where its height is greater than its cruising altitude, i.e. Rar is only able to fly over the ith mountain using the jth plane if H_i ≤ Y_j.

For the ith plane, please help Rar determine the total number of different flights he can possibly take, i.e. the total number of ways Rar can choose s and e such that s ≤ e, and there are no mountains between s and e inclusive of height greater than Y_i.

Your program must read from standard input.

The first line of input will contain two integers, N and Q.

The second line of input will contain N integers, H₁, . . . , H_N.

The third line of input will contain Q integers, Y₁, . . . , Y_Q.

Your program must print to standard output.

The output should contain Q lines with one integer each, with the number on the ith line indicating the total number of different flights Rar can take with his ith plane.

• 1 ≤ N, Q, H_i, Y_i ≤ 10⁶