On one of their infamous adventures, Morty ends up in a dangerous situation again. Luckily, Rick is able to save him using one of his gizmos. To return the favor, Morty decides to gift Megaseeds to Rick.
He decides to prepares num number of crates holding the seeds, numbered from 0 to num - 1. In the beginning, each crate K contains c_K number of Megaseeds.
It is perfectly acceptable if some of the crates are empty. However, Morty, being the nice guy, plans to include at least one non-empty crate. Rick, being the eccentric character, will only accept the gift if the number of seeds in each crate is multiple of an integer div where div > 1.
Summer joins Morty's plan and starts helping him out by redistributing the seeds to fit Rick's criteria. She can move a seed from crate i to either the preceding crate (if it exists) or to the crates after it (if they exist). Both Morty and Summer wish to complete this as soon as possible. Your task is to return the minimum number of operations that Summer needs to perform so that the gift meets Rick's criteria.
If the gift cannot be modified to meet Rick's standards, return -1.
Input Format
- The first line contains an integer
num, the number of crates. - The second line contains
numintegers, representing the initial number of seeds in each crate.
Output Format
Return the minimum number of operations required. If it is impossible to meet the criteria, return -1.
Example 1:
Input: num = 4, seeds = [0, 1, 0, 1]
Output: 2
Explanation:n/a
Example 2:
Input: num = 3, seeds = [1, 2, 3]
Output: 1
Explanation:n/a
- The number of crates,
1 <= num <= 10^6. - The initial number of seeds in each crate,
0 <= seeds[i] <= 10^6. - Out of
seeds[0],seeds[1],seeds[2], ...,seeds[num-1], at least one is assured to be greater than0.
input:
output: