Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Управо је завршен трећи круг вечерашње епизоде познате емисије Нокскру Гејм Шоу, и ваш омиљени трочлани тим, “Сањиве Занатлије”, губи резултатом 2-1, и тиме је пред испадањем. Због тога, морају однети победу у следећој игри: Спринт 4.
Игра Спринт 4 је трка која се састоји из \(N-1\) делова, у којима два играча трче по бројевној правој, брзином највише \(1\). На почетку трке, играчи се налазе на позицијама \(a_0\) и \(b_0\). У \(i\)-том делу трке, тркачи треба да стигну од своје тренутне позиције, до позиција \(a_i\) и \(b_i\). Рачуна се да су прешли \(i\)-ти део када се нађу на позицијама \(a_i\) и \(b_i\) у неком распореду (није битно који играч стоји на којој од две позиције). Када се тренутни део заврши, следећи одмах отпочиње и такмичари крећу са тренутних позиција ка новим циљевима. Трка се завршава када се заврши \(N-1\)-ви део трке.
Како је трка јако неизвесна, Занатлијама је потребна ваша помоћ. На вама је да одредите најмање могуће време да би завршили трку.
У првом реду улаза се налази природан број \(N\), дужина низова \(a\) и \(b\).
У сваком наредном реду се налазе
по два природна броја \(a_i\) и \(b_i\), који описују позиције циљева за
\(i\)-ти део трке.
На излаз исписати један број: најмање време потребно да би завршили трку.
Тест примери су подељени у 4 дисјунктних група:
5
1 5
6 2
3 7
8 4
5 84За прва \(3\) дела трке, сваки играч треба да се помери једно место удесно. У последњем делу, први играч треба да се помери једно место удесно (\(4\rightarrow5\)), док други треба да остане на својој позицији \(8\).