Rotating Sushi

Interview

Time limit1sMemory limit512 MB

Summary

On a circular belt of N sushi plates, find the maximum number of distinct kinds in any k consecutive plates, counting the coupon kind c once more if it is not already present.

Level: Medium5 of 10
Topics: Sliding window, Two pointers, Array, Hash map
Solved: No attempts yet

Problem

In a rotating sushi restaurant, various kinds of sushi sit on plates on a rotating belt, and customers pick out and eat the sushi they like. Representing each kind of sushi by a number, the figure below shows an example of the belt state in a rotating sushi restaurant. The belt may hold two or more pieces of the same kind of sushi.

A newly opened rotating sushi restaurant, struggling because of the recession, wants to raise its sales through the following two promotions.

Ordinarily, customers pick sushi freely and pay for however many pieces they eat, but if they eat k consecutive plates starting from any one position on the belt, the restaurant offers them at a discounted flat price.
The restaurant issues each customer a coupon with one kind of sushi written on it, and if the customer takes part in promotion 1, they receive one additional piece of the kind written on the coupon for free. If that kind is not currently on the belt, the chef makes it fresh and serves it to the customer.

We want to eat as many different kinds of sushi as possible by taking part in this discount promotion. Consider the example in the figure above. Suppose k=4 and the customer received a coupon for sushi number 30. Ignoring the coupon, the cases where 4 different kinds of sushi can be eaten are (9, 7, 30, 2), (30, 2, 7, 9), and (2, 7, 9, 25), three cases in all, but since sushi number 30 can be eaten additionally with the coupon, choosing (2, 7, 9, 25) lets the customer eat 5 kinds of sushi.

Given the belt state of a rotating sushi restaurant, the number of kinds of sushi on the menu, the number of plates eaten consecutively, and the coupon number, write a program that finds the maximum number of kinds of sushi the customer can eat.

Input

The first line gives N, the number of plates on the rotating sushi belt; d, the number of kinds of sushi; k, the number of plates eaten consecutively; and the coupon number c, each separated by one space. Here 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), and 1 ≤ c ≤ d. From the second line, N lines follow, each giving one integer from 1 to d representing the kind of sushi as you start from one position on the belt and follow the rotation direction.

Output

On one line, print the maximum number of kinds of sushi that can be eaten from the given rotating sushi belt.

Examples2

Example 1
Input
```
8 30 4 30
7
9
7
30
2
7
9
25
```
Expected output
```
5
```
Example 2
Input
```
8 50 4 7
2
7
9
25
7
9
7
30
```
Expected output
```
4
```