Bob 有 $N$ 个编程练习需要在他各自的截止日期前完成。每个练习 $i$ 完成仅需一个单位时间，但有一个截止日期 $d_i$ ($1 \le d_i \le N$)，表示必须在当前时间后的 $d_i$ 个单位时间内完成。

Bob 将按照序列 $a_1, a_2, \dots, a_N$ 的顺序完成这些练习，其中 $a_1$ 是他完成的第一个练习，$a_2$ 是第二个，以此类推。Bob 最初的计划由序列 $1, 2, \dots, N$ 描述。通过一次交换操作，Bob 可以交换该序列中相邻的两个数字。请问将该序列变为一个能按时完成所有练习的序列，最少需要多少次交换？

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 200\,000$)。下一行包含 $N$ 个空格分隔的整数 $d_1, d_2, \dots, d_N$ ($1 \le d_i \le N$)。

在总共 25 分的测试点中，有 17 分满足 $N \le 5000$。

输出格式

输出一个整数，表示 Bob 按时完成所有练习所需的最少交换次数；如果无法按时完成，则输出 $-1$。

样例

输入 1

4
4 4 3 2

输出 1

3

说明 1

一个合法的序列是 $(1, 4, 3, 2)$，它可以由 $(1, 2, 3, 4)$ 通过三次交换得到。

输入 2

3
1 1 3

输出 2

-1

说明 2

有两个练习的截止时间为 1，但在此时间内只能完成一个练习。