John lạc vào mê cung gồm ~n~ phòng đánh số từ 1 tới ~n~, trong mỗi phòng có một đèn điện. Mỗi đèn chỉ có đúng một công tắc và công tắc đèn ~i~ được đặt trong phòng \(~s_i~ (1 \leq ~s_i~ \leq n)\).
Ban đầu John ở phòng số 1 và đèn phòng đó sáng, đèn các phòng khác tắt. John có thể đi sang một phòng đã sáng đèn và khi đã vào phòng, John có thể tùy ý bật tắt các công tắc trong phòng đó. John cần đi sang phòng ~n~ trong tình trạng chỉ có đèn phòng ~n~ sáng, đèn các phòng khác đều tắt.

Yêu cầu

Cho biết thông tin về hệ thống đèn và công tắc, hãy xác định số lần chuyển phòng ít nhất John cần thực hiện để thực hiện yêu cầu trên.

Dữ liệu

Dòng 1: Chứa số nguyên ~n~.
Dòng 2: Chứa ~n~ số nguyên ~s_1,s_2,…,s_n~.

Kết quả

Một số nguyên là số lần chuyển phòng ít nhất cần thực hiện. Trong trường hợp không có phương án thực hiện yêu cầu, ghi ra số -1.

Giới hạn

\(2 \leq n \leq ~10^6~\).

Input

3
2 3 1

Output

3