Karaoke 2

Time limit2sMemory limit512 MB

Summary

Assign the unclaimed middle pitches to one of two singers to minimize how many times the microphone changes hands across the song.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy
Solved: No attempts yet

Problem

Yeongseon and Hyobin are singing in a karaoke room.

Pitches are numbered 1 through M, where 1 is the lowest pitch and M is the highest. Yeongseon can sing only the pitches from low to M. Hyobin can sing only the pitches from 1 to high.

Before the song starts, the two of them fix who takes each pitch. If Yeongseon takes pitch 3, then Yeongseon sings every 3 in the song and Hyobin never sings a 3. An assignment made this way holds until the song ends. Only Hyobin can sing a pitch below low and only Yeongseon can sing a pitch above high, so those pitches are already assigned.

The song is a sequence of N pitches. There is one microphone, and the singer who took the current pitch has to be holding it. The singer who took the first pitch starts with the microphone, and it passes to the other singer at every place where two neighboring pitches belong to different singers.

The number of passes depends on how the shared pitches are assigned. Write a program that finds the smallest number of passes.

Input

The first line contains N, M, low, and high. ( $1 \le N \le 1000$ , $1 \le M \le 1000$ , $1 \le \textit{low} \le M$ , $\textit{low} \le \textit{high} \le M$ )

The second line contains the N pitches of the song in order. Each pitch is an integer from 1 to M.

Output

Print the smallest number of microphone passes on the first line.

Examples4

Example 1
Input
```
6 3 2 2
1 2 3 2 1 2
```
Expected output
```
2
```
Example 2
Input
```
8 10 3 7
4 4 5 5 6 5 3 6
```
Expected output
```
0
```
Example 3
Input
```
6 6 2 5
5 3 1 6 4 2
```
Expected output
```
1
```
Example 4
Input
```
9 10 4 5
1 4 3 5 2 5 7 5 9
```
Expected output
```
3
```