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

#5327
다국어

교실에서 잠자기2 (Sleeping in Class) 2초 1024MB

문제

Bessie 소는 최근 대면 수업에 돌아오게 되어 매우 기뻤다! 그러나 그녀의 강사인 Farmer John은 매우 지루한 강사여서, Bessie는 수업 도중 자주 잠들게 된다.

Farmer John은 Bessie가 수업에 집중하지 않는 것을 알아차리고, 다른 학생인 Elsie에게 Bessie가 한 수업 동안 몇 번이나 잠드는지 기록해 달라고 부탁한다. 수업 기간은 총 N번 있으며 (2 ≤ N ≤ 10^5), Elsie는 Bessie가 i번째 수업에서 a_i번 (1 ≤ a_i ≤ 10^{18}) 잠들었다고 기록한다. 모든 수업 기간 동안 Bessie가 잠든 총 횟수는 최대 10^{18}이다.

Elsie는 Bessie와 경쟁심을 느껴, Farmer John에게 Bessie가 모든 수업에서 일정한 횟수만큼 잠드는 것처럼 보이게 만들어, 문제의 원인이 전적으로 Bessie에게 있다고 느끼게 하고자 한다.

Elsie가 기록을 수정할 수 있는 유일한 방법은 인접한 두 수업 기간을 합치거나 한 수업 기간을 두 개로 나누는 것이다. 예를 들어, 만약 a = [1, 2, 3, 4, 5]라면, Elsie가 두 번째와 세 번째 수업 기간을 합치면 기록은 [1, 5, 4, 5]가 된다. 이후 Elsie가 세 번째 수업 기간을 두 개로 나누면, 기록은 [1, 5, 0, 4, 5], [1, 5, 1, 3, 5], [1, 5, 2, 2, 5], [1, 5, 3, 1, 5] 또는 [1, 5, 4, 0, 5] 중 아무거나 될 수 있다.

Bessie가 가장 싫어하는 숫자의 후보 q_1, …, q_Q (1 ≤ Q ≤ 10^5, 1 ≤ q_i ≤ 10^{18})가 주어질 때, 각 후보마다 Elsie가 기록의 모든 숫자를 q_i로 만들기 위해 수행해야 하는 최소 수정 횟수를 계산하라. 불가능할 경우 -1을 출력하라.


입력

각 테스트 케이스의 첫 번째 줄에는 N이 주어지고, 두 번째 줄에는 a₁, a₂, …, a_N이 주어진다. 세 번째 줄에는 Q가 주어지며, 이후 Q개의 줄에 각각 Bessie가 가장 싫어하는 숫자 후보 q_i가 주어진다.


출력

각 q_i마다, 기록의 모든 항목을 q_i로 변환하기 위해 Elsie가 수행해야 하는 최소 수정 횟수를 출력하라. 불가능할 경우 -1을 출력하라.


예제1

입력
6

1 2 3 1 1 4

7

1

2

3

4

5

6

12
출력
6

6

4

5

-1

4

5

Elsie는 레코드의 모든 숫자를 3으로 변경하려면 최소한 4번의 작업이 필요합니다.

 

   1 2 3 1 1 4

-> 3 3 1 1 4

-> 3 3 1 5

-> 3 3 6

-> 3 3 3 3

 

Elsie가 레코드의 모든 숫자를 5로 변경하는 것은 불가능하므로 이 후보자의 답은 -1입니다. 


출처

USACO 2022 February Platinum

역링크 공식 문제집만