시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 3 1 1 33.333%

문제

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.

제한

  • 1 ≤ N, Q, Hi, Yi ≤ 106

예제 입력 1

6 3
1 3 2 4 1 2
2 3 4

예제 출력 1

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.

예제 입력 2

6 3
2 2 5 2 2 2
1 2 10

예제 출력 2

0
9
21

예제 입력 3

2 1
1 2
1000000

예제 출력 3

3