시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 114 | 49 | 36 | 40.000% |
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 Hi 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 Yi 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 Hi ≤ Yj.
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 Yi.
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, H1, . . . , HN.
The third line of input will contain Q integers, Y1, . . . , YQ.
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.
6 3 1 3 2 4 1 2 2 3 4
5 9 21
For the first plane, 5 flights are possible: (1, 1), (3, 3), (5, 5), (5, 6), (6, 6). For the second plane, 9 flights are possible: (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3), (5, 5), (5, 6), (6, 6). For the last plane, all 21 flights are possible.
6 3 2 2 5 2 2 2 1 2 10
0 9 21
2 1 1 2 1000000
3