시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 17 11 8 57.143%

문제

영선이와 효빈이는 노래를 부르러 노래방에 갔다.

음의 높이는 1부터 M 까지로 나누어져 있으며, 1이 낮은 음, M이 높은 음이다. 영선이는 low보다 크거나 같고, M보다 작거나 같은 음만 부를 수 있고, 효빈이는 1보다 크거나 같고, high보다 작거나 같은 음만 부를 수 있다.

두 사람은 서로 어떤 음을 부를지 결정했다. 예를 들어, 영선이가 3이라는 음을 부르기로 했다면, 노래에 3이 나올 때 마다 영선이가 그 부분을 불러야 하고, 효빈이는 절대로 3을 부를 수 없다.

노래는 음 N개의 연속으로 이루어져 있다. 마이크의 개수는 1개이고, 해당 음을 부를 수 있는 사람에게 마이크가 가있어야 한다.

노래를 부르기 위해 마이크의 주인을 바꿔야하는 횟수의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M, low, high가 주어진다. (1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000, 1 ≤ low ≤ M, low ≤ high ≤ M)

둘째 줄에는 노래의 음이 순서대로 주어진다. (1 ≤ 음 ≤ M)

출력

마이크의 주인을 바꿔야하는 횟수의 최소값

예제 입력 1

6 3 2 2
1 2 3 2 1 2

예제 출력 1

2

예제 입력 2

8 10 3 7
4 4 5 5 6 5 3 6

예제 출력 2

0

예제 입력 3

6 6 2 5
5 3 1 6 4 2

예제 출력 3

1

예제 입력 4

9 10 4 5
1 4 3 5 2 5 7 5 9

예제 출력 4

3

출처