月の瀬さんは悪魔らしいことをするため、街じゅうの樹木をスギの木に変えて、人々を花粉症で困らせることにした。
樹木は $N$ 種類存在する。$i$ 種類目の樹木の天界でのランクは $A_i$、魔界でのランクは $B_i$ である。また、$1$ 種類目の樹木はスギである。
月の瀬さんは、次の操作を何度でも行うことができる。
天界と魔界の移動や、その他の行動に時間はかからない。
それぞれの樹木の種類について、スギの木に変えるためにかかる最短の時間を求めよ。
1 行目に、$N$ が与えられる。
2 行目に、$A_1, A_2, A_3, \dots, A_N$ が空白区切りで与えられる。
3 行目に、$B_1, B_2, B_3, \dots, B_N$ が空白区切りで与えられる。
$N$ 行のうち $i$ 行目には、$i$ 種類目の樹木をスギの木に変えるための時間の最小値を出力せよ。
3 1 2 5 6 3 4
0 1 2
樹木 1 は元からスギの木なので、コストはかかりません。
樹木 2 を天界で樹木 1 に変えると、コストは $|A_1 - A_2| = |1 - 2| = 1$ です。
樹木 3 を魔界で樹木 2 に変えたのち、天界で樹木 1 に変えるとコストは $|B_3 - B_2| + |A_2 - A_1| = |4 - 3| + |1 - 2| = 2$ です。
5 1 10 5 6 9 2 3 4 7 8
0 1 2 3 2