Gahui and the 3-Step High Note

Interview

Time limit1.5sMemory limit256 MB

Summary

Given a sequence of notes and an arithmetic progression with first term A and difference D, find the largest number of terms of the progression that appear as a subsequence in order.

Level: Medium4 of 10
Topics: Greedy, Array, Two pointers, Implementation
Solved: No attempts yet

Problem

I'm in my dream~eam~eam ♬

Moved by the three-step high note, Gahui decided to attend a high note competition. Let us express the note names as numbers. We can think of '1st octave do' as 1, and each note one step higher has a number larger by 1. Singing high notes starting from note A and rising by D notes each time is expressed as an arithmetic sequence whose first term is A and common difference is D. When the number of terms in this arithmetic sequence is X, we call it an X-step high note. Below is a 6-step high note with A = 1 and D = 2.

This competition had a problem: because one or more participants sing high notes at the same time, the judges cannot evaluate them properly. So, given the participants' notes expressed as numbers in order, we want to find the largest X such that an X-step high note starting from note A and rising by D notes is possible. Write a program to help with this.

Input

The first line gives the integer N (1 ≤ N ≤ 2 x 10⁴), the number of participants' notes, and the integers A, D (1 ≤ A, D ≤ 10⁷), the first term and common difference of the high note, separated by spaces.

The second line gives N integers representing the participants' notes in order, separated by spaces. Each value is a positive integer not exceeding 10⁷.

Output

Print the largest X such that an X-step high note starting from note A and rising by D notes is possible.

Examples3

Example 1
Input
```
3 1 2
1 3 5
```
Expected output
```
3
```
Example 2
Input
```
3 1 2
3 1 5
```
Expected output
```
1
```
Example 3
Input
```
7 3 3
3 3 9 7 2 6 9
```
Expected output
```
3
```