32797번 - Sleeping on the Train 다국어

문제

Antonio is sightseeing in Line Town. Part of his sightseeing involves taking the famous Line Train. The Line Train goes through $n$ stops conveniently numbered from 1ドル$ to $n$. The path the Line Train takes involves starting at stop 1ドル,ドル then going to every stop in numerically increasing order until it reaches stop $n,ドル at which point it turns around and goes to every stop in numerically decreasing order until it reaches stop 1ドル,ドル where it turns around and repeats its journey. When the train gets to either stop 1ドル$ or stop $n,ドル it lets all passengers that want to disembark leave the train. It then turns around, and then allows new passengers to board before heading to the next stop.

Antonio is traveling from stop $a$ to stop $b$. Antonio is very sleepy, so he is not paying attention when he boards the train and could board a train initially heading in the wrong direction. Immediately upon boarding the train, he falls asleep and wakes up $t$ times during the trip. Each time he wakes up, he notices that he is somewhere between stop $s_i$ and $s_i+1$. Since he is very sleepy, he does not know which direction the train is traveling in. Also, since he is not presently at his destination, he immediately falls back asleep.

After the $t^\text{th}$ time waking up, Antonio decides he should stay awake for the rest of the trip. He stays on the train until the next time it stops at stop $b,ドル at which point he disembarks.

Compute the minimum number of times the train turned around while he was on it.

입력

The first line contains four integers, $n$ $(2 \le n \le 10^9),ドル $t$ $(1 \le t \le 10^5),ドル $a,ドル and $b$ (1ドル \le a, b \le n, a \neq b$).

The second line contains $t$ integers. The $i^\text{th}$ integer, $s_i$ $(1 \le s_i < n),ドル indicates that when Antonio woke up for the $i^\text{th}$ time, he was somewhere between stops $s_i$ and $s_i+1$.

출력

Output the minimum number of times the train turned around while he was on it.

제한

힌트