Cho mảng a gồm n số nguyên dương, trong 1 bước bạn có thể chọn 1 số i (1<=i<=n) và 1 số x

(1<=x<=10^9) và gán cho a(i) giá trị mới là a(i) mod x.

Tìm số bước biến đổi ít nhất để mảng a trở thành 1 hoán vị của các số 1,2,3,...,n.

Input:

Dòng đầu chứa số nguyên n(1<=n<=10^5).

Dòng thứ 2 chứa n số nguyên dương a1,a2,a3,...,an (1<=ai<=10^9).

Output:

In ra số bước biến đổi ít nhất, nếu không thể biến đổi mảng a thành hoán vị thì in ra -1.