题目

给你一个长度为n的由正整数组成的数组a，你可以自由地选择一个非负整数x，将x依次对数组a的每个元素进行取模，最终得到y，(x%a[1]%a[2]%...%a[n]=y)，请问y最多有多少种可能的值。

输入

第一行为n，表示数组元素的个数。(1<=n<=1e6)
第二行为数组a的各个元素。 (1<=a[i]<=1e9)

输出

一个整数，表示你的答案

Samples

3
5 3 2

2

Limitation

1s, 1024KiB for each test case.