Sieve Game

시간 제한1초메모리 제한1024 MB

요약

고른 번호의 배수 위치를 모두 1만큼 늘리거나 줄이는 연산으로 영 배열을 주어진 목표 배열로 바꾸는 최소 연산 횟수를 구한다.

난이도: 보통10점 중 6점
유형: 수학, 정수론, 그리디
정답자: 아직 제출이 없습니다

문제

Alice, after mastering the sieve of Eratosthenes, excitedly created a puzzle game that made use of it.

The rules of the puzzle game are as follows:

An array $p\_1,p\_2,\ldots ,p\_N$ is given where all $p\_i$ is initially $0$ .
A target array $t\_1,t\_2,\ldots ,t\_N$ is given. Her goal is to make $p\_i=t\_i$ for all $1\le i\le N$ .
Each time, she can perform one of the following two operations:
- Choose $i$ and increase $p\_j$ by $1$ for every $1\le j\le N$ that is a multiple of $i$ .
- Choose $i$ and decrease $p\_j$ by $1$ for every $1\le j\le N$ that is a multiple of $i$ .
She can repeat this process as much as she wants.

Alice aims to solve the puzzle using the fewest operations, showcasing her puzzle-solving skill. Please help Alice find the minimum number of operations to solve the puzzle.

입력

The first line contains one integer, $N$ .

The second line contains space-separated $N$ integers — elements of the array $t$ .

출력

Print out the minimum number of operations to solve the puzzle. If the puzzle is unsolvable, print -1.

제한

$1\le N\le 200\\, 000$
$-10^9\le t\_i\le 10^9\ (1\le i\le N)$
All values in the input are integers.

예제2

예제 1
입력
```
4
1 1 1 0
```
예상 출력
```
2
```
예제 2
입력
```
7
0 1 1 1 0 2 -1
```
예상 출력
```
3
```