B - L Robust IS Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1500 点

問題文

長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) と、非負整数 X,Y が与えられます。

以下の条件をともに満たす A の部分列 B=(B_1,B_2,\ldots,B_M) の長さ M の最大値を求めてください。

  • 2\le i\le M を満たすすべての整数 i に対して、B_i\ge B_{i-1}-X が成り立つ。
  • 3\le i\le M を満たすすべての整数 i に対して、B_i\ge B_{i-2}-(X+Y) が成り立つ。

制約

  • 1\le N\le 5\times 10^5
  • 1\le A_i\le 10^9
  • 0\le X,Y\le 10^9
  • 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N X Y
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

7 3 1
8 6 3 7 5 2 6

出力例 1

5

部分列 (8,6,7,5,6) は条件を満たします。 条件を満たす長さ 6 以上の部分列は存在しないので、5 を出力します。

入力例 2

5 0 0
5 4 3 2 1

出力例 2

1

入力例 3

15 441943320 890669835
693547414 783888993 702664735 345257171 73365711 320257375 683236857 951712144 151653382 210806164 439829968 987667432 978973992 565844495 621822141

出力例 3

13

Score : 1500 points

Problem Statement

You are given a length-N sequence of positive integers A=(A_1,A_2,\ldots,A_N) and non-negative integers X,Y.

Find the maximum length M of a subsequence B=(B_1,B_2,\ldots,B_M) of A that satisfies both of the following conditions.

  • B_i\ge B_{i-1}-X holds for every integer i satisfying 2\le i\le M.
  • B_i\ge B_{i-2}-(X+Y) holds for every integer i satisfying 3\le i\le M.

Constraints

  • 1\le N\le 5\times 10^5
  • 1\le A_i\le 10^9
  • 0\le X,Y\le 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N X Y
A_1 A_2 \ldots A_N

Output

Output the answer.

Sample Input 1

7 3 1
8 6 3 7 5 2 6

Sample Output 1

5

The subsequence (8,6,7,5,6) satisfies the conditions. There is no subsequence of length 6 or greater that satisfies the conditions, so output 5.

Sample Input 2

5 0 0
5 4 3 2 1

Sample Output 2

1

Sample Input 3

15 441943320 890669835
693547414 783888993 702664735 345257171 73365711 320257375 683236857 951712144 151653382 210806164 439829968 987667432 978973992 565844495 621822141

Sample Output 3

13