시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 159 73 61 58.095%

문제

페인팅 전문 회사 부키치 암즈는 거대한 페인팅용 롤러 "다이나믹 롤러"를 출시하였다. 이 신제품은 평범한 페인팅 롤러와 마찬가지로 굴려서 칠할 수 있지만, 손잡이를 세로로 휘둘러 잉크를 한번에 흩뿌릴 수도 있도록 설계되었다. 이러한 새로운 사용방법은 거대한 몸집과 맞물려 매우 역동적으로 보였기 때문에, 이 롤러의 이름은 다이나믹 롤러가 되었다. 평소 페인팅에 관심이 많던 멩미는 다이나믹 롤러의 매력에 흠뻑 빠져, 단숨에 다이나믹 롤러를 구매했다. 지금 당장 롤러를 시험해 보고 싶었던 멩미는 통로 일부분을 칠해보기로 했다.

통로는 1 × N 길이의 일자 형태를 가지고 있고, 통로의 바닥은 1 × 1 타일로 가득 차있다. 각 타일은 잉크지수 Ai 와 점도지수 Bi 를 가지고 있다. 타일이 제각각 다른 특성을 가지고 있기 때문에, 멩미는 세심하게 롤러를 휘둘러야만 한다. 멩미가 i 번째 타일 위에 서 있을 때, 멩미는 다이나믹 롤러로 현재 위치보다 오른쪽에 있으면서 점도지수가 서 있는 칸의 잉크지수 Ai 이하인 칸을 칠할 수 있다.

통로는 기본적인 관리가 되고 있기 때문에, 각 칸의 잉크지수 Ai 는 점도지수 Bi 이상이다. 그러나 깊숙한 통로는 관리에 어려움이 있기 때문에, 점도지수 Bi 는 항상 오름차순이다. 이런 상황 속에서 멩미가 통로의 각 타일에서 서 있을 때 다이나믹 롤러로 칠할 수 있는 최대의 칸 수를 구해보자.

입력

첫 번째 줄에 통로의 길이인 자연수 N이 입력으로 주어진다. (1 ≤ N ≤ 5 × 105)

두 번째 줄에 N개의 정수 A1, A2, ..., AN이 공백으로 구분되어 주어진다. Aii 번째 칸의 잉크지수를 의미한다. (1 ≤ Aᵢ ≤ 1018)

세 번째 줄에 N개의 정수 B1, B2, ..., BN이 공백으로 구분되어 주어진다. Bii 번째 칸의 점도지수를 의미한다. (1 ≤ Bᵢ ≤ 1018, AiBi)

B1, B2, ..., BN은 오름차순이다. 즉, 1 ≤ ijN을 만족하는 모든 정수 순서쌍 (i, j)에 대해 BiBj 가 성립한다.

출력

첫 번째 줄에 N개의 정수 x1, x2, ..., xN을 공백으로 구분하여 출력한다. xii 번째 칸에 서서 다이나믹 롤러를 사용할 때 최대로 칠할 수 있는 칸의 개수이다.

예제 입력 1

5
10 10 10 10 10
10 10 10 10 10

예제 출력 1

4 3 2 1 0

첫 번째 칸에서는 시작 지점의 잉크지수가 10이다. 두 번째 칸부터 다섯 번째 칸의 점도지수가 10이기에 다섯 번째 칸까지 칠할 수 있다. 그렇기에 총 4칸을 칠할 수 있다.

두 번째 칸도 똑같이 3칸, 세 번째 칸은 2칸, 네 번째 칸은 1칸, 다섯 번째 칸은 0칸 칠할 수 있다.

예제 입력 2

6
60 90 100 88 90 99
60 70 80 85 90 90

예제 출력 2

0 4 3 0 1 0

첫 번째 칸의 잉크지수는 60이다. 60보다 작거나 같은 점도지수를 가진 가장 오른쪽 칸이 첫 번째 칸이므로 답은 0칸이다.

두 번째 칸의 잉크지수는 90이다. 여섯 번째이자 마지막 칸의 점도지수가 90이므로 여섯 번째 칸까지 칠할 수 있으므로 답은 4칸이다.

세 번째 칸의 잉크지수는 100이다. 마찬가지로 여섯 번째 칸까지 칠할 수 있으므로 답은 3칸이다.

네 번째 칸의 잉크지수는 88이다. 88보다 작거나 같은 점도지수를 가진 가장 오른쪽 칸은 네 번째 칸이므로 답은 0칸이다.

다섯 번째 칸의 잉크지수는 90이다. 90보다 작거나 같은 점도지수를 가진 칸은 가장 오른쪽 칸은 여섯 번째 칸이므로 답은 1칸이다.

여섯 번째 칸의 잉크지수는 99이며, 99보다 작거나 같은 점도지수를 가진 칸은 가장 오른쪽 칸은 여섯 번째 칸이므로 답은 0칸이다.