시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVhYzFjXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuIFx1ZDNmNFx1Yzc0MCBcdWM3NzQgXHVjOTExIFx1YmE4NyBcdWFjMWNcdWI5N2MgXHVhY2U4XHViNzdjXHVjMTFjIFx1Y2Q5NFx1Y2Q5Y1x1ZDU2MCBcdWM2MDhcdWM4MTVcdWM3ODVcdWIyYzhcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1Y2Q1Y1x1Yzg4NSBcdWFjYjBcdWFjZmNcdWJiM2NcdWM3NTggXHVjOWM4XHVjNzc0IFx1Yzg4Ylx1YzU0NFx1YzU3YyBcdWQ1NjAgXHVhYzgzXHVjNzg1XHViMmM4XHViMmU0LiBcdWFjYjBcdWFjZmNcdWJiM2NcdWM3NTggXHVjOWM4XHVjNzc0IFx1Yzg4Ylx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQsIFx1Y2VlNFx1ZDUzY1x1Y2Y2OVx1YjRlNFx1Yzc1OCBcdWM4ODVcdWI5NTgoXHVjODE1XHVjMjE4XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQyOVx1YjJjOFx1YjJlNC4pXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMThcdWM1ZjRcdWM3NTggXHViZDgwXHViZDg0XHVjMjE4XHVjNWY0XHVjNzQ0IDxlbT5BPFwvZW0+XHViNzdjXHVhY2UwIFx1ZDU1OFx1YmE3NCwgMiBcdWM3NzRcdWMwYzFcdWM3NTggXHViYWE4XHViNGUwIGkgXHVjNWQwIFx1YjMwMFx1ZDU3NCZuYnNwOzxlbT5BPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPiZ0aGluc3A7LSZ0aGluc3A7MTxcL3N1Yj4mdGhpbnNwOyZlcXVpdjsmdGhpbnNwOzxlbT5BPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPjxcL3N1Yj4mbmJzcDsoPGVtPm1vZDxcL2VtPiZuYnNwOzxlbT5rPFwvZW0+KSZuYnNwO1x1YjA5OCZuYnNwOzxlbT5BPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPiZ0aGluc3A7LSZ0aGluc3A7MTxcL3N1Yj4mdGhpbnNwOy0mdGhpbnNwOzxlbT5kPFwvZW0+JnRoaW5zcDsmbGU7JnRoaW5zcDs8ZW0+QTxcL2VtPjxzdWI+PGVtPmk8XC9lbT48XC9zdWI+JnRoaW5zcDsmbGU7JnRoaW5zcDs8ZW0+QTxcL2VtPjxzdWI+PGVtPmk8XC9lbT4mdGhpbnNwOy0mdGhpbnNwOzE8XC9zdWI+JnRoaW5zcDsrJnRoaW5zcDs8ZW0+ZDxcL2VtPlx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NjhcdWM3NDQgXHViNzNiXHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQzZjRcdWM3NDQgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzljOFx1Yzc3NCBcdWM4OGJcdWM3NDAgXHVjZWU0XHVkNTNjIFx1Y2Q5NFx1Y2Q5Y1x1YmIzYyBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc0MCBcdWNlZTRcdWQ1M2NcdWNmNjlcdWM3NDQgXHVhY2UwXHViOTdjIFx1YjU0YyBcdWFkZjggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YzhmY1x1YzEzOFx1YzY5NC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgPGVtPk48XC9lbT4sIDxlbT5rPFwvZW0+IFx1YzY0MCA8ZW0+ZDxcL2VtPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuJm5ic3A7KDEmdGhpbnNwOyZsZTsmdGhpbnNwOzxlbT5OPFwvZW0+JnRoaW5zcDsmbGU7JnRoaW5zcDs1JnRoaW5zcDsmdGltZXM7JnRoaW5zcDsxMDxzdXA+NTxcL3N1cD4sJnRoaW5zcDsxJnRoaW5zcDsmbGU7JnRoaW5zcDs8ZW0+azxcL2VtPiwmdGhpbnNwOzxlbT5kPFwvZW0+JnRoaW5zcDsmbGU7JnRoaW5zcDs1JnRoaW5zcDsmdGltZXM7JnRoaW5zcDsxMDxzdXA+NTxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPjxlbT5OPFwvZW0+XHVhYzFjXHVjNzU4IFx1Y2VlNFx1ZDUzY1x1Y2Y2OVx1Yzc1OCBcdWMyMWNcdWMxMWNcdWM2NDAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVhZTM4XHVjNzc0IDxlbT5OPFwvZW0+XHVjNzU4IFx1YmMzMFx1YzVmNCA8ZW0+UzxcL2VtPlx1YWMwMCBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4mbmJzcDsoMSZ0aGluc3A7JmxlOyZ0aGluc3A7PGVtPlM8XC9lbT48c3ViPjxlbT5pPFwvZW0+PFwvc3ViPiZ0aGluc3A7JmxlOyZ0aGluc3A7NSZ0aGluc3A7JnRpbWVzOyZ0aGluc3A7MTA8c3VwPjU8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzljOFx1Yzc3NCBcdWM4OGJcdWM3NDAgXHVjZWU0XHVkNTNjIFx1Y2Q5NFx1Y2Q5Y1x1YmIzYyBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc0MCBcdWNlZTRcdWQ1M2NcdWNmNjlcdWM3NDQgXHVhY2UwXHViOTdjIFx1YjU0YyBcdWFkZjggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU2OVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNTY0OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikhhcm1vbnkiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGlzIGEmbmJzcDtzZXF1ZW5jZSA8ZW0+UzxcL2VtPiB3aXRoIDxlbT5OPFwvZW0+IG51bWJlcnMuIFlvdSB3aWxsIG1ha2UgYSBzdWJzZXF1ZW5jZSBvZiA8ZW0+UzxcL2VtPiB0aGF0IG1ha2VzIGEgaGFybW9ueS48XC9wPlxyXG5cclxuPHA+QSBzZXF1ZW5jZSA8ZW0+QTxcL2VtPiBtYWtlcyBhIGhhcm1vbnkgaWYgZm9yIGV2ZXJ5IDxlbT5pPFwvZW0+IGdyZWF0ZXIgdGhhbiBvciBlcXVhbCB0byB0aGFuIDIsIDxlbT5BPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPiZ0aGluc3A7LSZ0aGluc3A7MTxcL3N1Yj4mdGhpbnNwOyZlcXVpdjsmdGhpbnNwOzxlbT5BPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPjxcL3N1Yj4mbmJzcDsoPGVtPm1vZDxcL2VtPiZuYnNwOzxlbT5rPFwvZW0+KSZuYnNwO29yIDxlbT5BPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPiZ0aGluc3A7LSZ0aGluc3A7MTxcL3N1Yj4mdGhpbnNwOy0mdGhpbnNwOzxlbT5kPFwvZW0+JnRoaW5zcDsmbGU7JnRoaW5zcDs8ZW0+QTxcL2VtPjxzdWI+PGVtPmk8XC9lbT48XC9zdWI+JnRoaW5zcDsmbGU7JnRoaW5zcDs8ZW0+QTxcL2VtPjxzdWI+PGVtPmk8XC9lbT4mdGhpbnNwOy0mdGhpbnNwOzE8XC9zdWI+JnRoaW5zcDsrJnRoaW5zcDs8ZW0+ZDxcL2VtPi4gRmluZCB0aGUgbG9uZ2VzdCBzdWJzZXF1ZW5jZSBvZiA8ZW0+UzxcL2VtPiB0aGF0IG1ha2VzIGEgaGFybW9ueS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPjxlbT5OPFwvZW0+LCA8ZW0+azxcL2VtPiBhbmQgPGVtPmQ8XC9lbT4gaXMgZ2l2ZW4gYXQgdGhlIGZpcnN0IGxpbmUuICgxJnRoaW5zcDsmbGU7JnRoaW5zcDs8ZW0+TjxcL2VtPiZ0aGluc3A7JmxlOyZ0aGluc3A7NSZ0aGluc3A7JnRpbWVzOyZ0aGluc3A7MTA8c3VwPjU8XC9zdXA+LCZ0aGluc3A7MSZ0aGluc3A7JmxlOyZ0aGluc3A7PGVtPms8XC9lbT4sJnRoaW5zcDs8ZW0+ZDxcL2VtPiZ0aGluc3A7JmxlOyZ0aGluc3A7NSZ0aGluc3A7JnRpbWVzOyZ0aGluc3A7MTA8c3VwPjU8XC9zdXA+KTxcL3A+XHJcblxyXG48cD5BcnJheSA8ZW0+UzxcL2VtPiBpcyBnaXZlbiB3aXRoIDxlbT5OPFwvZW0+IG51bWJlcnMgaW4gdGhlIHNlY29uZCBsaW5lLiAoMSZ0aGluc3A7JmxlOyZ0aGluc3A7PGVtPlM8XC9lbT48c3ViPjxlbT5pPFwvZW0+PFwvc3ViPiZ0aGluc3A7JmxlOyZ0aGluc3A7NSZ0aGluc3A7JnRpbWVzOyZ0aGluc3A7MTA8c3VwPjU8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSBsZW5ndGggb2YgdGhlIGxvbmdlc3Qgc3Vic2VxdWVuY2Ugb2YgPGVtPlM8XC9lbT4gdGhhdCBtYWtlcyBhIGhhcm1vbnkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처