#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
template < class S, class T> inline S max_L( S a,T b) {
return a>= b? a: b;
}
template < class S, class T> inline S chmax( S & a, T b) {
if ( a< b) {
a= b;
}
return a;
}
#define main dummy_main
int main( ) {
return 0 ;
}
#undef main
int dp[ 20001 ] ;
class Solution{
public :
int longestSubsequence( vector< int > & A, int D) {
int Lj4PdHRW, i;
int N = A.size ( ) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
A[ i] + = 10000 ;
}
for ( i= ( 0 ) ; i< ( 20001 ) ; i++ ) {
dp[ i] = - 1 ;
}
for ( Lj4PdHRW= ( 0 ) ; Lj4PdHRW< ( N) ; Lj4PdHRW++ ) {
auto & i = A[ Lj4PdHRW] ;
dp[ i] = 1 ;
if ( 0 <= i- D && i- D <= 20000 ) {
chmax( dp[ i] , dp[ i- D] + 1 ) ;
}
}
{
int KL2GvlyY;
int Q5VJL1cS;
if ( 20001 == 0 ) {
Q5VJL1cS = 0 ;
}
else {
Q5VJL1cS = dp[ 0 ] ;
for ( KL2GvlyY= ( 1 ) ; KL2GvlyY< ( 20001 ) ; KL2GvlyY++ ) {
Q5VJL1cS = max_L( Q5VJL1cS, dp[ KL2GvlyY] ) ;
}
}
return Q5VJL1cS;
}
}
}
;
// cLay varsion 20191102-1
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
// int dp[20001];
//
// class Solution {
// public:
// int longestSubsequence(vector<int>& A, int D) {
// int N = A.size();
//
// rep(i,N) A[i] += 1d4;
// rep(i,20001) dp[i] = -1;
//
// rep[A](i,N){
// dp[i] = 1;
// if(0 <= i-D <= 2d4) dp[i] >?= dp[i-D] + 1;
// }
//
// return max(dp(20001));
// }
// };
I3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPZmFzdCIpCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnRlbXBsYXRlPGNsYXNzIFMsIGNsYXNzIFQ+IGlubGluZSBTIG1heF9MKFMgYSxUIGIpewogIHJldHVybiBhPj1iP2E6YjsKfQp0ZW1wbGF0ZTxjbGFzcyBTLCBjbGFzcyBUPiBpbmxpbmUgUyBjaG1heChTICZhLCBUIGIpewogIGlmKGE8Yil7CiAgICBhPWI7CiAgfQogIHJldHVybiBhOwp9CiNkZWZpbmUgbWFpbiBkdW1teV9tYWluCmludCBtYWluKCl7CiAgcmV0dXJuIDA7Cn0KI3VuZGVmIG1haW4KaW50IGRwWzIwMDAxXTsKY2xhc3MgU29sdXRpb257CiAgcHVibGljOgogIGludCBsb25nZXN0U3Vic2VxdWVuY2UodmVjdG9yPGludD4mIEEsIGludCBEKXsKICAgIGludCBMajRQZEhSVywgaTsKICAgIGludCBOID0gQS5zaXplKCk7CiAgICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgICAgQVtpXSArPSAxMDAwMDsKICAgIH0KICAgIGZvcihpPSgwKTtpPCgyMDAwMSk7aSsrKXsKICAgICAgZHBbaV0gPSAtMTsKICAgIH0KICAgIGZvcihMajRQZEhSVz0oMCk7TGo0UGRIUlc8KE4pO0xqNFBkSFJXKyspewogICAgICBhdXRvICZpID0gQVtMajRQZEhSV107CiAgICAgIGRwW2ldID0gMTsKICAgICAgaWYoMCA8PSBpLUQgICYmICBpLUQgPD0gMjAwMDApewogICAgICAgIGNobWF4KGRwW2ldLCBkcFtpLURdICsgMSk7CiAgICAgIH0KICAgIH0KICAgIHsKICAgICAgaW50IEtMMkd2bHlZOwogICAgICBpbnQgUTVWSkwxY1M7CiAgICAgIGlmKDIwMDAxPT0wKXsKICAgICAgICBRNVZKTDFjUyA9IDA7CiAgICAgIH0KICAgICAgZWxzZXsKICAgICAgICBRNVZKTDFjUyA9IGRwWzBdOwogICAgICAgIGZvcihLTDJHdmx5WT0oMSk7S0wyR3ZseVk8KDIwMDAxKTtLTDJHdmx5WSsrKXsKICAgICAgICAgIFE1VkpMMWNTID0gbWF4X0woUTVWSkwxY1MsIGRwW0tMMkd2bHlZXSk7CiAgICAgICAgfQogICAgICB9CiAgICAgIHJldHVybiBRNVZKTDFjUzsKICAgIH0KICB9Cn0KOwovLyBjTGF5IHZhcnNpb24gMjAxOTExMDItMQoKLy8gLS0tIG9yaWdpbmFsIGNvZGUgLS0tCi8vICNkZWZpbmUgbWFpbiBkdW1teV9tYWluCi8vIHt9Ci8vICN1bmRlZiBtYWluCi8vIAovLyBpbnQgZHBbMjAwMDFdOwovLyAKLy8gY2xhc3MgU29sdXRpb24gewovLyBwdWJsaWM6Ci8vICAgaW50IGxvbmdlc3RTdWJzZXF1ZW5jZSh2ZWN0b3I8aW50PiYgQSwgaW50IEQpIHsKLy8gICAgIGludCBOID0gQS5zaXplKCk7Ci8vIAovLyAgICAgcmVwKGksTikgQVtpXSArPSAxZDQ7Ci8vICAgICByZXAoaSwyMDAwMSkgZHBbaV0gPSAtMTsKLy8gCi8vICAgICByZXBbQV0oaSxOKXsKLy8gICAgICAgZHBbaV0gPSAxOwovLyAgICAgICBpZigwIDw9IGktRCA8PSAyZDQpIGRwW2ldID4/PSBkcFtpLURdICsgMTsKLy8gICAgIH0KLy8gCi8vICAgICByZXR1cm4gbWF4KGRwKDIwMDAxKSk7Ci8vICAgfQovLyB9Owo=