TLE '17 Contest 3 P2 - Sectors
View as PDF
Fax McClad, Croneria's most overpowered bounty hunter, has infiltrated the Dankey Kang Gang hideout!
The hideout contains  sectors, numbered from 
 to 
. Fax must visit 
 sectors for various reasons, such as confiscating goods, or defeating henchmen. The 
 sector that he must visit is sector 
. Note that Fax might have to visit a sector more than once.
The  sectors are connected in a single straight line. The 
 sector in the line is sector number 
. It is guaranteed that 
 if 
. Fax starts at the first sector he needs to visit and is only allowed to travel to sectors connected to the current one that he is in. That is, if Fax is in sector 
, he can only go to sector 
 or 
, if they exist. Note that sectors 
 and 
 are not connected if 
.
Fax wants to visit the  sectors in order, while going through a minimal number of sectors. This count is increased by one every time Fax walks through a sector, regardless if he has already went through it or not.
Can you tell him the minimum number of times that he must go through a sector?
Input Specification
The first line will contain  
 and 
 
.
 lines of input will follow. The 
 line will contain 
.
 lines of input will follow. The 
 line will contain 
.
For  of the points, 
.
It is recommended to use 64-bit integers (long long in C++, int64 in Pascal, long in Java) when computing the answer.
Output Specification
Output a single integer, the minimum number of times he must go through a sector.
Sample Input 1
4 4
1
2
3
4
1
4
2
3
Sample Output 1
7
Explanation for Sample Output 1
Fax can go through the sectors in the following order: . Therefore, he went through 
 sectors.
Sample Input 2
4 4
2
3
1
4
1
4
2
3
Sample Output 2
6
Comments