Minimum power loss

3.2

10 votes
Datastructures, Dynamic Programming, Algorithms, C++
Problem

There are two friends who live in a city. The city consists of N buildings that are numbered from 1 to N from left to right. One day, another friend starts coming to the city. On each ith day, this friend is found in a building Ai. It is the duty of two friends to bring home the third friend. Now, one of the friends goes to that building and bring the third friend home. While moving from one building to another building, the two friends lose some power.

For example, if one of these friends moves from building b1to building b2, then the loss of power is equal to |b2b1|. Here, |cd| means the absolute difference between c and d.

This continued for D days. Initially, the friends are at building X and Y and when a friend brings home another friend at building bi, then he stays there.

Now, these friends need your help in calculating the total minimum power loss.

Note: You cannot skip searching for the friend on any of the days.

Input format

  • The first line contains four integers N, D, X, and Y where N is the number of buildings in the city, D is the number of fays for which the search continues, and X and Yare the initial building number of two friends.
  • The second line contains D integers where the ith integer Ai is the building number in which the third friend is found on the ith day.

Output format

Print the single integer denoting the minimum total amount of power loss after all D days.

Constraints

1N2e51D2e51X, YN1AiN

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Initially X = 2 and Y = 5

Now on Day 1 evil is in the building 1 so, the warrior X will go to building 1 with lose of 1 ( 2 -> 1 )

On Day 2 evil is in building 2 so, the warrior X will go to building 2 with lose of 1 (1 -> 2)

On Day 3 evil is in building 6 so the warrior Y will go to building 6 with lose of 1 (5 -> 6)

On Day 3 evil is in building 4 so the warrior Y will go to building 4 with lose of 2 (6 -> 4)

Total power lose is 1 + 1 + 1 + 2 = 5.

Editor Image

?