Background

Special for beginners, ^_^

Description

有个群里有 $N（\le3000）$ 人，他们在一起发红包。

每次选一个群里最富的人，他出 $N$ 元，1 元被平台拿走，剩下的其他人每人得到 1 元。

如果平台里面所有人都发不起 $N$ 元红包，则结束。问一共可以发多少次红包。

Format

Input

本题包含多组数据。每组数据占 2 行，直到文件结束。

第一行一个正整数，表示群里的人数（根据腾讯限制，最多只能3000人大群）。

接下来给出群里每个成员的初始财富数量（不超过 $10^{18}$）。

Output

每行输出一组数据的答案。

Samples

3
11 45 14
2
114 514

67
627

Limitation

1s, 1024KiB for each test case.