조종사

시간 제한1초메모리 제한512 MB

요약

각 고도 제한에 대해 최댓값이 그 제한 이하인 부분 배열의 개수를 센다.

난이도: 보통10점 중 7점
유형: 스택, 정렬, 누적 합, 배열
정답자: 아직 제출이 없습니다

문제

Rar the Cat은 어릴 적 꿈이었던 조종사가 되어 친구 Dinosaur를 경치 좋은 비행에 몇 번 데려가려고 한다. Rar가 사는 세계는 일차원이며, N개의 정수로 나타낼 수 있다. i번째 정수 $H_i$ 는 세계의 가장 왼쪽 끝에서부터 i번째 산의 높이이다.

예를 들어 $N = 6$ , $H = \{1, 3, 2, 4, 1, 2\}$ 인 세계는 다음과 같다.

Rar에게는 자랑할 비행기가 총 Q대 있고, i번째 비행기의 최대 순항 고도는 $Y_i$ 미터이다. 각 비행은 s번째 산에서 출발해 e번째 산에서 끝난다. $s \le e$ , 즉 Rar는 항상 오른쪽으로만 난다고 가정한다. 모든 비행기에는 최대 순항 고도가 있으므로, 높이가 순항 고도보다 큰 산을 가로질러 날거나 그런 산에서 이륙하거나 착륙할 수 없다. 즉 Rar가 j번째 비행기로 i번째 산 위를 날 수 있으려면 $H_i \le Y_j$ 여야 한다.

i번째 비행기에 대해, Rar가 가능한 모든 비행의 수, 즉 $s \le e$ 이고 s부터 e까지(양 끝 포함) 높이가 $Y_i$ 보다 큰 산이 없는 모든 (s, e) 쌍의 수를 구하라.

입력

프로그램은 표준 입력에서 읽는다.

첫째 줄에는 두 정수 N과 Q가 주어진다.

둘째 줄에는 N개의 정수 $H_1, \dots, H_N$ 이 주어진다.

셋째 줄에는 Q개의 정수 $Y_1, \dots, Y_Q$ 가 주어진다.

출력

프로그램은 표준 출력에 쓴다.

출력은 Q개의 줄로 이루어지고, 각 줄에 정수 하나씩을 출력한다. i번째 줄의 수는 Rar가 i번째 비행기로 할 수 있는 서로 다른 비행의 총 개수이다.

제한

$1 \le N, Q, H_i, Y_i \le 10^6$

예제3

예제 1
입력
```
6 3
1 3 2 4 1 2
2 3 4
```
예상 출력
```
5
9
21
```
예제 2
입력
```
6 3
2 2 5 2 2 2
1 2 10
```
예상 출력
```
0
9
21
```
예제 3
입력
```
2 1
1 2
1000000
```
예상 출력
```
3
```