Nyctophobia

問題文

$1$ から $N$ までの番号が付いた $N$ 個のマスがあり、各 $i\ (1 \le i \lt N)$ についてマス $i$ とマス $i+1$ は隣り合っています。最初、全てのマスの色は黒であり、Vil君はマス $1$ にいます。Vil君がマス $i$ にいるとき、行える操作は以下の $2$ 種類です。

• 操作 $1$ : マス $L_i$ からマス $R_i$ までの色を白黒反転する。
• 操作 $2$ : マス $i$ が白であるとき、隣り合う白いマスに移動する。

何回か操作を行ってマス $N$ に行くとき、操作 $1$ を行う回数の最小値を求めてください。マス $N$ に行くことが不可能な場合はそのことを報告してください。

制約

• 入力はすべて整数
• $2 \le N \le 2 \times 10^5$
• $1 \le L_i \le R_i \le N$

入力

N
L_1 R_1
L_2 R_2
...
L_N R_N

出力

マス $N$ に到達可能なら操作 $1$ を行う回数の最小値を、そうでなければ -1 を出力し、最後に改行してください。

入力例1

5
1 2
3 5
1 3
4 4
1 5

出力例1

2

マス $1$ で操作 $1$ を行う $\rarr$ 操作 $2$ を行い、マス $2$ まで移動する $\rarr$ マス $2$ で操作 $1$ を行う $\rarr$ 操作 $2$ を(連続して)行い、マス $5$ まで移動する

この順序が最適で、操作 $1$ の回数の最小値は $2$ です。

入力例2

5
1 5
2 3
5 5
5 5
2 2

出力例2

1

入力例3

8
1 7
6 7
6 8
8 8
4 6
5 7
3 8
2 5

出力例3

2