入り浸り / Difficulty:4
Target time:40 min

問題文

Techくんは、暇さえあれば動画投稿サイトTechTubeに入り浸っています。

TechTubeを見すぎていると自覚し始めたTechくんは、
これまでどれだけの時間TechTubeを視聴したのか計算してみることにしました。

Techくんは、これまでに$N$回動画を視聴していおり、
それぞれの動画について視聴開始時刻、視聴終了時刻を記録していました。

しかし、記録されているデータを確認すると、視聴開始時刻と視聴終了時刻のデータが混在しており、
さらにデータの順序がばらばらになってしまっていました。
$i(1 \leqq i \leqq 2N)$番目のデータは、時刻$T_i$を表しています。

Techくんが視聴した動画数$N$と、視聴開始時刻と視聴終了時刻が混在した、
$2N$個分の時刻データが与えられます。
Techくんの代わりに、動画の総視聴時間$times$を求めて、出力してください。

  • Techくんは、一度に一つの動画のみを視聴しているものとします。
  • 視聴開始時刻$T_A$、視聴終了時刻$T_B$の場合、視聴時間は$T_B - T_A$として計算してください。
  • 入力・出力が$32$ビット符号付き整数の範囲を超える場合があることに注意してください。

入力される値


N
T_1 T_2 ... T_2N
  • 一行目に、Techくんが視聴した動画の数$N$が与えられます。
  • 二行目に、混在した$2N$個分の時刻データ$T_i$が与えられます。

期待される出力値


times
  • 一行で、動画の総視聴時間$times$を出力してください。

制約


  • 入力は全て整数
  • $1 \leqq N \leqq 10^4$
  • $1 \leqq T_i \leqq 10^{12}$
  • $j \neq k$ならば$T_j \neq T_k$
Sample Case1
Stdin
3
1 9 44 16 7 20
Expected
37
Description

以下の説明では、時刻$T_A$から時刻$T_B$まで動画を視聴することを$T_A \to T_B$と表します。
Techくんは、$1 \to 7, 9 \to 16, 20 \to 44$と$3$つの動画を視聴しました。
このとき、動画の視聴時間の合計は$37$となります。
一度に視聴している動画は一つだけなので、$1 \to 9, 16 \to 44, 7 \to 20$や、$1 \to 44, 7 \to 20, 9 \to 16$のように動画を視聴することはできません。

Sample Case2
Stdin
2
1 500000000000 500000000001 1000000000000
Expected
999999999998
Description

入力・出力が$32$ビット符号付き整数の範囲を超えるようなケースがあることに注意してください。

Sample Case3
Stdin
10
833662942 150739295 743045244 306893300 55395331 996084693 173035256 997084349 37280269 329113174 906401275 204935994 155438062 888912141 989318986 424217586 951153427 207367571 685810438 400217216
Expected
634209237

Python3 (3.7.3)

C11 (GCC 8.3.0)

C++17 (GCC 8.3.0)

Objective-C (GCC 8.3.0)

Java11 (OpenJDK 11.0.4)

PHP7.3 (PHP 7.3.10)

C#7.0 (Mono 5.20.1.19)

Python2.7 (2.7.16)

Ruby2.5 (2.5.7)

swift 5

Kotlin 1.3.40

Go 1.12 (1.12.12)

Perl5

JavaScript(Node.js8.16.2)

Rust1.34 (1.34.2)

Scala2.12.8

R 3.6.0

Racket6(6.12)

Sample Case

Sample Case1

Stdin
3
1 9 44 16 7 20
Expected
37

Run Code

Sample Case2

Stdin
2
1 500000000000 500000000001 1000000000000
Expected
999999999998

Run Code

Sample Case3

Stdin
10
833662942 150739295 743045244 306893300 55395331 996084693 173035256 997084349 37280269 329113174 906401275 204935994 155438062 888912141 989318986 424217586 951153427 207367571 685810438 400217216
Expected
634209237

Run Code

Stdin

1 2 3

Output

1 2 3

Stdin

1 2 3

1 2 3

Output

1 2 3

1 2 3

Stdin

yamada

taro

24

Output

"yamada taro is 24 years old!"

Stdin

1 2 3

Output

1

2

3