Description

Jiajia's teacher wrote a sequence of $n$ positive integers on the blackboard and asked Jiajia to perform the following operation: each time, erase two numbers $a$ and $b$, then add a number $a\times b+1$ to the sequence. Repeat this process until only one number remains. Among all the numbers obtained in this way, the largest is denoted as $\max$, the smallest as $\min$, and the range of the sequence is defined as $M = \max - \min$.

Since Jiajia is busy preparing for final exams, please help him calculate the corresponding range $M$ for the given sequence.

Input Format

The first line contains a positive integer $n$ indicating the length of the positive integer sequence.
The next $n$ lines each contain a positive integer.
A line with a single $0$ follows, indicating the end of the data.

Output Format

Output consists of a single line, the corresponding range $d$.

Sample 1

3
1
2
3
0

2

Data Range and Hint

For all data, $0\le n\le 50000$, and it is guaranteed that all calculations fit within the range of a 32-bit signed integer.