시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB3211108733.080%

문제

디지털 음악에서 소리는 대기압의 변화를 나타내는 숫자로 표현한다. 대기압의 변화는 일정한 시간 구간을 정해놓고, 연속되는 구간동안 얼마나 빠르게 변했는지를 측정한다. 이렇게 측정한 값을 샘플이라고 한다.

음성 처리에서 가장 중요한 단계는 녹음된 소리를 사일런스 기준으로 사일런스가 아닌 구간으로 나누는 작업이다. 너무 많은 조각이 나는 것을 방지 하기 위해서 사일런스는 최저값과 최고값의 차이가 c를 넘지않는 샘플 m개의 연속이라고 정의한다.

샘플 n개 이루어진 레코딩과 m과 c가 주어졌을 때, 사일런스를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 샘플의 수 n (1 ≤ n ≤ 1,000,000), m (1 ≤ m ≤ 10,000), c (0 ≤ c ≤ 10,000)가 주어진다.

둘째 줄에는 각 샘플의 값 ai가 주어진다. (0 ≤ ai ≤ 1,000,000 for 1 ≤ i ≤ n)

출력

max(a[i . . . i+m−1])−min(a[i . . . i+m−1]) ≤ c를 만족하는 모든 i를 오름차순으로 한 줄에 하나씩 출력한다.

만약, 주어진 입력에 사일런스가 없다면, NONE을 출력한다.

예제 입력 1

7 2 0
0 1 1 2 3 2 2

예제 출력 1

2
6

힌트

W3sicHJvYmxlbV9pZCI6IjI0MzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJUaGUgU291bmQgb2YgU2lsZW5jZSIsImRlc2NyaXB0aW9uIjoiPHA+XHViNTE0XHVjOWMwXHVkMTM4IFx1Yzc0Y1x1YzU0NVx1YzVkMFx1YzExYyBcdWMxOGNcdWI5YWNcdWIyOTQgXHViMzAwXHVhZTMwXHVjNTU1XHVjNzU4IFx1YmNjMFx1ZDY1NFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMjJiXHVjNzkwXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1Y1x1YjJlNC4gXHViMzAwXHVhZTMwXHVjNTU1XHVjNzU4IFx1YmNjMFx1ZDY1NFx1YjI5NCBcdWM3N2NcdWM4MTVcdWQ1NWMgXHVjMmRjXHVhYzA0IFx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWM4MTVcdWQ1NzRcdWIxOTNcdWFjZTAsIFx1YzVmMFx1YzE4ZFx1YjQxOFx1YjI5NCBcdWFkNmNcdWFjMDRcdWIzZDlcdWM1NDggXHVjNWJjXHViOWM4XHViMDk4IFx1YmU2MFx1Yjk3NFx1YWM4YyBcdWJjYzBcdWQ1ODhcdWIyOTRcdWM5YzBcdWI5N2MgXHVjZTIxXHVjODE1XHVkNTVjXHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVjZTIxXHVjODE1XHVkNTVjIFx1YWMxMlx1Yzc0NCBcdWMwZDhcdWQ1MGNcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NGNcdWMxMzEgXHVjYzk4XHViOWFjXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM5MTFcdWM2OTRcdWQ1NWMgXHViMmU4XHVhY2M0XHViMjk0IFx1YjE3OVx1Yzc0Y1x1YjQxYyBcdWMxOGNcdWI5YWNcdWI5N2MgXHVjMGFjXHVjNzdjXHViN2YwXHVjMmE0IFx1YWUzMFx1YzkwMFx1YzczY1x1Yjg1YyBcdWMwYWNcdWM3N2NcdWI3ZjBcdWMyYTRcdWFjMDAgXHVjNTQ0XHViMmNjIFx1YWQ2Y1x1YWMwNFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzc0XHViMmU0LiBcdWIxMDhcdWJiMzQgXHViOWNlXHVjNzQwIFx1Yzg3MFx1YWMwMVx1Yzc3NCBcdWIwOThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YmMyOVx1YzljMCBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzBhY1x1Yzc3Y1x1YjdmMFx1YzJhNFx1YjI5NCBcdWNkNWNcdWM4MDBcdWFjMTJcdWFjZmMgXHVjZDVjXHVhY2UwXHVhYzEyXHVjNzU4IFx1Y2MyOFx1Yzc3NFx1YWMwMCBjXHViOTdjIFx1YjExOFx1YzljMFx1YzU0YVx1YjI5NCBcdWMwZDhcdWQ1MGMgbVx1YWMxY1x1Yzc1OCBcdWM1ZjBcdWMxOGRcdWM3NzRcdWI3N2NcdWFjZTAgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwZDhcdWQ1MGMgblx1YWMxYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViODA4XHVjZjU0XHViNTI5XHVhY2ZjIG1cdWFjZmMgY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYWNcdWM3N2NcdWI3ZjBcdWMyYTRcdWI5N2MgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBkOFx1ZDUwY1x1Yzc1OCBcdWMyMTggbiZuYnNwOygxICZsZTsmbmJzcDtuICZsZTsgMSwwMDAsMDAwKSwgbSAoMSAmbGU7IG0gJmxlOyAxMCwwMDApLCBjICgwICZsZTsgYyAmbGU7IDEwLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMwZDhcdWQ1MGNcdWM3NTggXHVhYzEyIGE8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMCAmbGU7IGE8c3ViPmk8XC9zdWI+ICZsZTsgMSwwMDAsMDAwIGZvciAxICZsZTsgaSAmbGU7IG4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+bWF4KGFbaSAuIC4gLiBpK20mbWludXM7MV0pJm1pbnVzO21pbihhW2kgLiAuIC4gaSttJm1pbnVzOzFdKSAmbGU7IGNcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YmFhOFx1YjRlMCBpXHViOTdjIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCwgXHVjOGZjXHVjNWI0XHVjOWM0IFx1Yzc4NVx1YjgyNVx1YzVkMCBcdWMwYWNcdWM3N2NcdWI3ZjBcdWMyYTRcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0LCA8Y29kZT5OT05FPFwvY29kZT5cdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8aWZyYW1lIHdpZHRoPVwiNTYwXCIgaGVpZ2h0PVwiMzE1XCIgc3JjPVwiaHR0cHM6XC9cL3d3dy55b3V0dWJlLmNvbVwvZW1iZWRcL05BRXBwRlVXTGZjXCIgdGl0bGU9XCJZb3VUdWJlIHZpZGVvIHBsYXllclwiIGZyYW1lYm9yZGVyPVwiMFwiIGFsbG93PVwiYWNjZWxlcm9tZXRlcjsgYXV0b3BsYXk7IGNsaXBib2FyZC13cml0ZTsgZW5jcnlwdGVkLW1lZGlhOyBneXJvc2NvcGU7IHBpY3R1cmUtaW4tcGljdHVyZVwiIGFsbG93ZnVsbHNjcmVlbj48XC9pZnJhbWU+Iiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyNDMzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIFNvdW5kIG9mIFNpbGVuY2UiLCJkZXNjcmlwdGlvbiI6IjxwPkluIGRpZ2l0YWwgcmVjb3JkaW5nLCBzb3VuZCBpcyBkZXNjcmliZWQgYnkgYSBzZXF1ZW5jZSBvZiBudW1iZXJzIHJlcHJlc2VudGluZyB0aGUgYWlyIHByZXNzdXJlLCBtZWFzdXJlZCBhdCBhIHJhcGlkIHJhdGUgd2l0aCBhIGZpeGVkIHRpbWUgaW50ZXJ2YWwgYmV0d2VlbiBzdWNjZXNzaXZlIG1lYXN1cmVtZW50cy4gRWFjaCB2YWx1ZSBpbiB0aGUgc2VxdWVuY2UgaXMgY2FsbGVkIGEgc2FtcGxlLjxcL3A+XHJcblxyXG48cD5BbiBpbXBvcnRhbnQgc3RlcCBpbiBtYW55IHZvaWNlLXByb2Nlc3NpbmcgdGFza3MgaXMgYnJlYWtpbmcgdGhlIHJlY29yZGVkIHNvdW5kIGludG8gY2h1bmtzIG9mIG5vbi1zaWxlbmNlIHNlcGFyYXRlZCBieSBzaWxlbmNlLiBUbyBhdm9pZCBhY2NpZGVudGFsbHkgYnJlYWtpbmcgdGhlIHJlY29yZGluZyBpbnRvIHRvbyBmZXcgb3IgdG9vIG1hbnkgcGllY2VzLCB0aGUgc2lsZW5jZSBpcyBvZnRlbiBkZWZpbmVkIGFzIGEgc2VxdWVuY2Ugb2YgbSBzYW1wbGVzIHdoZXJlIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIGxvd2VzdCBhbmQgdGhlIGhpZ2hlc3QgdmFsdWUgZG9lcyBub3QgZXhjZWVkIGEgY2VydGFpbiB0cmVzaG9sZCBjLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdG8gZGV0ZWN0IHNpbGVuY2UgaW4gYSBnaXZlbiByZWNvcmRpbmcgb2YgbiBzYW1wbGVzIGFjY29yZGluZyB0byB0aGUgZ2l2ZW4gcGFyYW1ldGVyIHZhbHVlcyBtIGFuZCBjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGZpbGUgY29udGFpbnMgdGhyZWUgaW50ZWdlcnM6IG4gKDEgJmxlOyBuICZsZTsgMSwwMDAsMDAwKSwgdGhlIG51bWJlciBvZiBzYW1wbGVzIGluIHRoZSByZWNvcmRpbmc7IG0gKDEgJmxlOyBtICZsZTsgMTAsMDAwKSwgdGhlIHJlcXVpcmVkIGxlbmd0aCBvZiB0aGUgc2lsZW5jZTsgYW5kIGMgKDAgJmxlOyBjICZsZTsgMTAsMDAwKSwgdGhlIG1heGltYWwgbm9pc2UgbGV2ZWwgYWxsb3dlZCB3aXRoaW4gc2lsZW5jZS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIHRoZSBmaWxlIGNvbnRhaW5zIG4gaW50ZWdlcnMgYTxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBhPHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCBmb3IgMSAmbGU7IGkgJmxlOyBuKSwgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXM6IHRoZSBzYW1wbGVzIGluIHRoZSByZWNvcmRpbmcuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBzaG91bGQgbGlzdCBhbGwgdmFsdWVzIG9mIGkgc3VjaCB0aGF0IG1heChhW2kgLiAuIC4gaSttJm1pbnVzOzFdKSAmbWludXM7IG1pbihhW2kgLiAuIC4gaSttJm1pbnVzOzFdKSBcdTAwMTQmbHQ7PSBjLiBUaGUgdmFsdWVzIHNob3VsZCBiZSBsaXN0ZWQgaW4gaW5jcmVhc2luZyBvcmRlciwgZWFjaCBvbiBhIHNlcGFyYXRlIGxpbmUuPFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGlzIG5vIHNpbGVuY2UgaW4gdGhlIGlucHV0LCB3cml0ZSBOT05FIG9uIHRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIHRoZSBvdXRwdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2007 3번