시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 64 MB 48 21 17 48.571%

문제

추출하는 폴은 바리스타입니다. 폴에게는 커피콩 N개가 순서대로 주어집니다. 폴은 이 중 몇 개를 골라서 추출할 예정입니다. 이때, 최종 결과물의 질이 좋아야 할 것입니다. 결과물의 질이 좋기 위해서는, 커피콩들의 종류(정수로 표현됩니다.)로 이루어진 수열의 부분수열을 A라고 하면, 2 이상의 모든 i 에 대해 Ai - 1 ≡ Ai (mod k) 나 Ai - 1 - d ≤ Ai ≤ Ai - 1 + d를 만족함을 뜻합니다.

폴을 위해서 질이 좋은 커피 추출물 중 가장 많은 커피콩을 고를 때 그 개수를 구해주세요.

입력

첫째 줄에 N, kd가 주어집니다. (1 ≤ N ≤ 5 × 105, 1 ≤ k, d ≤ 5 × 105)

N개의 커피콩의 순서와 각각의 번호를 나타내는 길이 N의 배열 S가 다음 줄에 주어집니다. (1 ≤ Si ≤ 5 × 105)

출력

질이 좋은 커피 추출물 중 가장 많은 커피콩을 고를 때 그 개수를 출력합니다.

예제 입력 1

9 7 2
1 5 12 10 8 6 4 4 3

예제 출력 1

8
W3sicHJvYmxlbV9pZCI6IjE1NjQ4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjZDk0XHVjZDljXHVkNTU4XHViMjk0IFx1ZDNmNFx1YjNjNCBcdWJjMTRcdWI5YWNcdWMyYTRcdWQwYzBcdWM3ODVcdWIyYzhcdWIyZTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Y2Q5NFx1Y2Q5Y1x1ZDU1OFx1YjI5NCBcdWQzZjRcdWM3NDAgXHViYzE0XHViOWFjXHVjMmE0XHVkMGMwXHVjNzg1XHViMmM4XHViMmU0LiBcdWQzZjRcdWM1ZDBcdWFjOGNcdWIyOTQgXHVjZWU0XHVkNTNjXHVjZjY5IDxlbT5OPFwvZW0+XHVhYzFjXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuIFx1ZDNmNFx1Yzc0MCBcdWM3NzQgXHVjOTExIFx1YmE4NyBcdWFjMWNcdWI5N2MgXHVhY2U4XHViNzdjXHVjMTFjIFx1Y2Q5NFx1Y2Q5Y1x1ZDU2MCBcdWM2MDhcdWM4MTVcdWM3ODVcdWIyYzhcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjZDVjXHVjODg1IFx1YWNiMFx1YWNmY1x1YmIzY1x1Yzc1OCBcdWM5YzhcdWM3NzQgXHVjODhiXHVjNTQ0XHVjNTdjIFx1ZDU2MCBcdWFjODNcdWM3ODVcdWIyYzhcdWIyZTQuIFx1YWNiMFx1YWNmY1x1YmIzY1x1Yzc1OCBcdWM5YzhcdWM3NzQgXHVjODhiXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCwgXHVjZWU0XHVkNTNjXHVjZjY5XHViNGU0XHVjNzU4IFx1Yzg4NVx1Yjk1OChcdWM4MTVcdWMyMThcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDI5XHViMmM4XHViMmU0LilcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWJkODBcdWJkODRcdWMyMThcdWM1ZjRcdWM3NDQgPGVtPkE8XC9lbT5cdWI3N2NcdWFjZTAgXHVkNTU4XHViYTc0LCAyIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWJhYThcdWI0ZTAgaSBcdWM1ZDAgXHViMzAwXHVkNTc0Jm5ic3A7PGVtPkE8XC9lbT48c3ViPjxlbT5pPFwvZW0+JnRoaW5zcDstJnRoaW5zcDsxPFwvc3ViPiZ0aGluc3A7JmVxdWl2OyZ0aGluc3A7PGVtPkE8XC9lbT48c3ViPjxlbT5pPFwvZW0+PFwvc3ViPiZuYnNwOyg8ZW0+bW9kPFwvZW0+Jm5ic3A7PGVtPms8XC9lbT4pJm5ic3A7XHViMDk4Jm5ic3A7PGVtPkE8XC9lbT48c3ViPjxlbT5pPFwvZW0+JnRoaW5zcDstJnRoaW5zcDsxPFwvc3ViPiZ0aGluc3A7LSZ0aGluc3A7PGVtPmQ8XC9lbT4mdGhpbnNwOyZsZTsmdGhpbnNwOzxlbT5BPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPjxcL3N1Yj4mdGhpbnNwOyZsZTsmdGhpbnNwOzxlbT5BPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPiZ0aGluc3A7LSZ0aGluc3A7MTxcL3N1Yj4mdGhpbnNwOysmdGhpbnNwOzxlbT5kPFwvZW0+XHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU2OFx1Yzc0NCBcdWI3M2JcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDNmNFx1Yzc0NCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjOWM4XHVjNzc0IFx1Yzg4Ylx1Yzc0MCBcdWNlZTRcdWQ1M2MgXHVjZDk0XHVjZDljXHViYjNjIFx1YzkxMSBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1Y2VlNFx1ZDUzY1x1Y2Y2OVx1Yzc0NCBcdWFjZTBcdWI5N2MgXHViNTRjIFx1YWRmOCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTc0XHVjOGZjXHVjMTM4XHVjNjk0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCA8ZW0+TjxcL2VtPiwgPGVtPms8XC9lbT4gXHVjNjQwIDxlbT5kPFwvZW0+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4mbmJzcDsoMSZ0aGluc3A7JmxlOyZ0aGluc3A7PGVtPk48XC9lbT4mdGhpbnNwOyZsZTsmdGhpbnNwOzUmdGhpbnNwOyZ0aW1lczsmdGhpbnNwOzEwPHN1cD41PFwvc3VwPiwmdGhpbnNwOzEmdGhpbnNwOyZsZTsmdGhpbnNwOzxlbT5rPFwvZW0+LCZ0aGluc3A7PGVtPmQ8XC9lbT4mdGhpbnNwOyZsZTsmdGhpbnNwOzUmdGhpbnNwOyZ0aW1lczsmdGhpbnNwOzEwPHN1cD41PFwvc3VwPik8XC9wPlxyXG5cclxuPHA+PGVtPk48XC9lbT5cdWFjMWNcdWM3NTggXHVjZWU0XHVkNTNjXHVjZjY5XHVjNzU4IFx1YzIxY1x1YzExY1x1YzY0MCBcdWFjMDFcdWFjMDFcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWFlMzhcdWM3NzQgPGVtPk48XC9lbT5cdWM3NTggXHViYzMwXHVjNWY0IDxlbT5TPFwvZW0+XHVhYzAwIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiZuYnNwOygxJnRoaW5zcDsmbGU7JnRoaW5zcDs8ZW0+UzxcL2VtPjxzdWI+PGVtPmk8XC9lbT48XC9zdWI+JnRoaW5zcDsmbGU7JnRoaW5zcDs1JnRoaW5zcDsmdGltZXM7JnRoaW5zcDsxMDxzdXA+NTxcL3N1cD4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjOWM4XHVjNzc0IFx1Yzg4Ylx1Yzc0MCBcdWNlZTRcdWQ1M2MgXHVjZDk0XHVjZDljXHViYjNjIFx1YzkxMSBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1Y2VlNFx1ZDUzY1x1Y2Y2OVx1Yzc0NCBcdWFjZTBcdWI5N2MgXHViNTRjIFx1YWRmOCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE1NjQ4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSGFybW9ueSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgaXMgYSZuYnNwO3NlcXVlbmNlIDxlbT5TPFwvZW0+IHdpdGggPGVtPk48XC9lbT4gbnVtYmVycy4gWW91IHdpbGwgbWFrZSBhIHN1YnNlcXVlbmNlIG9mIDxlbT5TPFwvZW0+IHRoYXQgbWFrZXMgYSBoYXJtb255LjxcL3A+XHJcblxyXG48cD5BIHNlcXVlbmNlIDxlbT5BPFwvZW0+IG1ha2VzIGEgaGFybW9ueSBpZiBmb3IgZXZlcnkgPGVtPmk8XC9lbT4gZ3JlYXRlciB0aGFuIG9yIGVxdWFsIHRvIHRoYW4gMiwgPGVtPkE8XC9lbT48c3ViPjxlbT5pPFwvZW0+JnRoaW5zcDstJnRoaW5zcDsxPFwvc3ViPiZ0aGluc3A7JmVxdWl2OyZ0aGluc3A7PGVtPkE8XC9lbT48c3ViPjxlbT5pPFwvZW0+PFwvc3ViPiZuYnNwOyg8ZW0+bW9kPFwvZW0+Jm5ic3A7PGVtPms8XC9lbT4pJm5ic3A7b3IgPGVtPkE8XC9lbT48c3ViPjxlbT5pPFwvZW0+JnRoaW5zcDstJnRoaW5zcDsxPFwvc3ViPiZ0aGluc3A7LSZ0aGluc3A7PGVtPmQ8XC9lbT4mdGhpbnNwOyZsZTsmdGhpbnNwOzxlbT5BPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPjxcL3N1Yj4mdGhpbnNwOyZsZTsmdGhpbnNwOzxlbT5BPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPiZ0aGluc3A7LSZ0aGluc3A7MTxcL3N1Yj4mdGhpbnNwOysmdGhpbnNwOzxlbT5kPFwvZW0+LiBGaW5kIHRoZSBsb25nZXN0IHN1YnNlcXVlbmNlIG9mIDxlbT5TPFwvZW0+IHRoYXQgbWFrZXMgYSBoYXJtb255LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+PGVtPk48XC9lbT4sIDxlbT5rPFwvZW0+IGFuZCA8ZW0+ZDxcL2VtPiBpcyBnaXZlbiBhdCB0aGUgZmlyc3QgbGluZS4gKDEmdGhpbnNwOyZsZTsmdGhpbnNwOzxlbT5OPFwvZW0+JnRoaW5zcDsmbGU7JnRoaW5zcDs1JnRoaW5zcDsmdGltZXM7JnRoaW5zcDsxMDxzdXA+NTxcL3N1cD4sJnRoaW5zcDsxJnRoaW5zcDsmbGU7JnRoaW5zcDs8ZW0+azxcL2VtPiwmdGhpbnNwOzxlbT5kPFwvZW0+JnRoaW5zcDsmbGU7JnRoaW5zcDs1JnRoaW5zcDsmdGltZXM7JnRoaW5zcDsxMDxzdXA+NTxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPkFycmF5IDxlbT5TPFwvZW0+IGlzIGdpdmVuIHdpdGggPGVtPk48XC9lbT4gbnVtYmVycyBpbiB0aGUgc2Vjb25kIGxpbmUuICgxJnRoaW5zcDsmbGU7JnRoaW5zcDs8ZW0+UzxcL2VtPjxzdWI+PGVtPmk8XC9lbT48XC9zdWI+JnRoaW5zcDsmbGU7JnRoaW5zcDs1JnRoaW5zcDsmdGltZXM7JnRoaW5zcDsxMDxzdXA+NTxcL3N1cD4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgdGhlIGxlbmd0aCBvZiB0aGUgbG9uZ2VzdCBzdWJzZXF1ZW5jZSBvZiA8ZW0+UzxcL2VtPiB0aGF0IG1ha2VzIGEgaGFybW9ueS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처