페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5861
서브태스크

인터캐스텔러 2초 1024MB

문제

때는 30XX 년. 과학자·기술자의 끊임없는 노력으로 우주의 다른 행성 간의 교류가 활발히 이루어지게 되었다.

비버 비타로는 이성인에게 지구의 음식을 소개하는 앰배서더를 맡고 있으며, 오늘 오후 1시에 JOI 별을 향해 출발할 예정이다.

이번 JOI 성인에게 소개하는 음식 중 하나로서 잘라낸 카스테라가 준비되어 있다. 카스텔라는 밀가루에 닭고기 달걀, 설탕, 물을 넣고 스폰지 모양으로 통통하게 구운 과자이다.

카스텔라는 가로로 길어진 직육면체의 형태를 하고 있으며, 종 방향의 틈을 따라 N개의 조각으로 분할되어 있다. 왼쪽에서 i 번째 (1≤i≤N) 조각의 길이는 정수 A_i입니다.

마지막으로 JOI 성인은 짝수에 혐오감을 보인다는 것이 밝혀졌다. 따라서 해결책으로 길이가 짝수인 조각이 없을 때까지 다음 일련의 작업을 반복하기로 결정했습니다.

1. 길이가 짝수 조각 중 가장 오른쪽에 있는 것을 선택합니다.

2. 선택한 조각을 세로로 자르고 이등분한다. 즉, 선택한 조각의 길이를 k로 설정하면 위치를 변경하지 않고 길이 \frac k2 조각으로 나눕니다.

작업이 올바르게 수행되었는지 확인하기 위해 Bitaro는 Q 개의 질문을 준비했습니다. j 번째 (1≤j≤Q)의 질문은 다음과 같습니다.

• 모든 작업이 끝나면 왼쪽에서 X_j 번째 조각의 길이는 무엇입니까?

카스텔라와 질문에 대한 정보가 주어지면 각 질문에 대한 답변을 찾는 프로그램을 작성하십시오.


입력

입력은 아래와 같은 형식으로 주어지며, 모든 입력은 정수이다.

N

A_1

A_2
\vdots

A_N

Q

X_1

X_2

\vdots

X_Q

[제한]

1 ≤ N ≤ 200\,000

1 ≤ A_i ≤ 1\,000\,000\,000 (1 ≤ i ≤ N).

1 ≤ Q ≤ 200\,000.

1 ≤ X_j ≤ 1\,000\,000\,000\,000\,000 (= 10^{15}) (1 ≤ j ≤ Q).

X_j ≤ X_{j+1} (1 ≤ j ≤ Q - 1).

모든 작업이 완료된 후 카스텔라는 최소 X_Q 조각으로 절단됩니다.


부분문제

번호 점수 조건
#125점

 A_i ≤ 8 (1 ≤ i ≤ N).

#235점

 N ≤ 1\,000, Q ≤ 1\,000.

#340점

추가 제한 없음


예제1

입력
4
14
9
8
12
6
2
3
5
7
11
13
출력
7
9
1
1
1
3

처음에는 카스텔라 조각의 길이가 왼쪽부터 14, 9, 8, 12 이다.

모든 작업이 완료된 후 카스텔라는 15 조각으로 절단되는데, 조각의 길이는 왼쪽에서 부터 7, 7, 9, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3 이다.


예제2

입력
13
1
4
1
4
2
1
3
5
6
2
3
7
3
8
2
10
11
13
15
17
18
20
출력
1
1
1
1
5
3
1
3

예제3

입력
16
536870912
402653184
536870912
536870912
134217728
536870912
671088640
536870912
536870912
536870912
939524096
805306368
536870912
956301312
536870912
536870912
5
2500000000
3355443201
4294967296
5111111111
6190792704
출력
5
1
7
57
1

출처

JOI 2022

역링크