madirony52   1년 전

문제

암소 베시(Bessie)는 최근 대면 수업에 복귀하게 되어 매우 기뻤습니다! 그러나 그녀의 강사인 파머 존(Farmer John)의 강의가 워낙 지루해서, 베시는 수업 중에 자주 졸아버립니다.

파머 존은 베시가 수업에 집중하지 못하고 있다는 사실을 알아채고, 반 친구 엘시(Elsie)에게 각 수업 시간마다 베시가 졸은 횟수를 기록하도록 부탁했습니다. 총 수업 기간은 N회 (1 <= N <= 105)이고, 엘시는 i번째 수업 동안 베시가 졸은 횟수를 ai (0 <= ai <= 106)로 기록합니다. 수업 기간 전체에 걸쳐 베시가 졸은 시간의 총합도 106이 넘지 않습니다.

엘시는 경쟁심이 강해서, 파머 존에게 "베시는 매 수업마다 똑같이 졸았다"고 믿게 만들고 싶습니다. 엘시가 기록을 조작할 수 있는 유일한 방법은 인접한 두 수업 기록을 합치는 것뿐입니다.

예를 들어 a = [1,2,3,4,5] 에서 2번째와 3번째 기록을 합치면 [1,5,4,5]가 됩니다.

이제 엘시는 주어진 기록을 모두 같은 숫자 q로 바꾸려 하는데, 이때 필요한 최소 합치기 횟수를 구하려 합니다.

입력

입력은 T(1 <= T <= 10)개의 독립적인 테스트 케이스로 이루어집니다.

첫째 줄에 테스트 케이스 개수 T, 이후 각 테스트 케이스마다

첫번째 줄에는 정수 N (수업의 수)

두번째 줄에는 a1, a2, ..., aN 이 주어집니다.

각 테스트 케이스마다 배열 a에 들어 있는 모든 값의 합이 106만 이하임이 보장됩니다. 또한, 모든 테스트 케이스에 걸쳐 N의 합이 105을 넘지 않음이 보장됩니다.

출력

각 테스트 케이스에 대해 기록을 모두 같게 만들기 위해 엘시가 수행해야 하는 최소 수정 횟수를 한 줄에 하나씩, 총 T줄에 걸쳐 출력하세요.

힌트

첫 번째 테스트 케이스에서 엘시는 3번의 수정으로 모든 기록을 3으로 통일할 수 있습니다.

두 번째 테스트 케이스에서는 엘시는 2번의 수정으로 모든 기록을 7로 만들 수 있습니다.

마지막 테스트 케이스에서는 이미 모든 항목이 같으므로, 어떠한 작업도 수행할 필요가 없습니다.

댓글을 작성하려면 로그인해야 합니다.