Lưu ý: Bài toán này không chia Subtask.

Cho dãy hoán vị ~p~ độ dài ~n~. Bạn có thể thực hiện thao tác sau với bất kỳ số lần nào ~(~có thể không thực hiện~)~:

• Chọn một đoạn liên tiếp ~[l,r]~ ~(1 \le l \le r \le n)~ thỏa mãn ~r-l+1 < n~, tiến hành sắp xếp các phần tử trên đoạn này theo bất kỳ thứ tự nào.

Bạn hãy thực hiện thao tác trên với số lần ít nhất để sắp xếp dãy hoán vị ~p~ theo thứ tự tăng dần.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên của dãy ~p~ ~(1 \le p_i \le n)~.
• Dữ liệu đảm bảo dãy ~p~ là một dãy hoán vị hợp lệ.

Output

• In ra số lần thực hiện thao tác ít nhất. Nếu không thể sắp xếp dãy hoán vị theo thứ tự tăng dần, in ra ~-1~.

Examples

Sample Input

5
2 1 4 5 3

Sample Output

2

Notes

Trong ví dụ, các thao tác được thực hiện như sau:

• Chọn đoạn ~[l,r]=[3,5]~ và sắp xếp đoạn này để dãy hoán vị trở thành ~p=[2,1,3,4,5]~.
• Chọn đoạn ~[l,r]=[1,2]~ và sắp xếp đoạn này để dãy hoán vị trở thành ~p=[1,2,3,4,5]~.