\(𝑁\)개의 톱니바퀴가 있다.

\(𝑁\)개의 톱니바퀴에는 \(1\)부터 \(𝑁\)까지 번호가 있고, \(i\)번째 톱니바퀴는 \(i+1\)번째 톱니바퀴와 연결되어 있다. \(i\) \((1 \le i < 𝑁)\)

우리는 첫 번째 톱니바퀴만 회전 시킬 수 있다.

우리의 목적은 \(𝑁\)번째 톱니바퀴를 한 바퀴 회전 시키는 것이다.

톱니바퀴의 수 \(𝑁\)과 각 톱니바퀴의 톱니 수가 주어질 때, \(𝑁\)번째 톱니바퀴를 1바퀴 회전 시키기 위해 첫 번째 톱니바퀴를 최소 몇 바퀴 회전 시켜야 하는 지 출력하라.

예를 들어, 총 \(3\)개의 톱니바퀴가 있고 각각의 톱니 수를 \(16\)개, \(8\)개, \(4\)개라고 하자.

3개의 톱니바퀴는 아래처럼 맞물려 있다.

첫 번째 톱니바퀴가 \(1\) 바퀴 회전하면, 두 번째 톱니바퀴가 \(2\) 바퀴 회전하고, 세 번째 톱니바퀴는 \(4\) 바퀴 회전한다.

따라서, 세 번째 톱니바퀴를 \(1\) 바퀴 회전 시키기 위해 첫 번째 톱니바퀴를 최소 \(1\) 바퀴 회전시켜야 한다.

입력 설명

첫 번째 줄에는 톱니바퀴의 수 \(𝑁\)이 주어진다. \(𝑁\)은 \(2\) 이상 \(100\) 이하의 정수이다.

두 번째 줄에는 각 톱니바퀴의 톱니 수가 공백을 사이에 두고 주어진다. 톱니 수는 \(2\) 이상 \(10000\) 이하의 정수이다.

출력 설명

\(𝑁\)번째 톱니바퀴를 한 바퀴 회전 시키기 위해 첫 번째 톱니바퀴를 최소 \(k\)번 회전 시켜야 할 때, \(k\)를 출력해라. \(k\) 는 정수이다.

예제 입력 1

3
16 8 4

예제 출력 1

1

예제 입력 2

2
3 5

예제 출력 2

2

예제 입력 3

3
10 5 2

예제 출력 3

1