문제
어떤 수열에서, 연속된 3개의 수를 보았을 때, 그 수가 단조증가 수열이거나, 단조감소 수열인 경우가 없으면 이 수열을 "지그재그 수열" 이라고 말한다.
좀 더 정확하게는, 길이 N의 수열 A가 모든 1 이상 N-2 이하의 자연수 i에 대해서, Ai ≤ Ai+1 ≤ Ai+2도 만족하지 않고, Ai ≥ Ai+1 ≥ Ai+2도 만족하지 않으면, A는 지그재그 수열이다.
길이 N의 수열 A가 주어졌을 때, A의 연속된 부분 수열 중 지그재그 수열의 최대 길이를 구하여라.
길이 M의 B가 길이 N인 A의 연속된 부분 수열이라는 것은, 어떤 i가 존재 해서, B1 = Ai, B2 = Ai+1, ..., BM = Ai+M-1 인 것을 말한다.
출력
A의 연속된 부분 수열 중 지그재그 수열의 최대 길이를 구하여라.
제한
- 3 ≤ N ≤ 5,000
- 1 ≤ Ai ≤ 109 (1 ≤ i ≤ N)
W3sicHJvYmxlbV9pZCI6IjE1Nzc5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiWmlnemFnIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI1YTQgXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjLCBcdWM1ZjBcdWMxOGRcdWI0MWMgM1x1YWMxY1x1Yzc1OCBcdWMyMThcdWI5N2MgXHViY2Y0XHVjNTU4XHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1YzIxOFx1YWMwMCBcdWIyZThcdWM4NzBcdWM5OWRcdWFjMDAgXHVjMjE4XHVjNWY0XHVjNzc0XHVhYzcwXHViMDk4LCBcdWIyZThcdWM4NzBcdWFjMTBcdWMxOGMmbmJzcDtcdWMyMThcdWM1ZjRcdWM3NzggXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzVjNlx1YzczY1x1YmE3NCBcdWM3NzQgXHVjMjE4XHVjNWY0XHVjNzQ0ICZxdW90OzxzdHJvbmc+XHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzIxOFx1YzVmNDxcL3N0cm9uZz4mcXVvdDsgXHVjNzc0XHViNzdjXHVhY2UwIFx1YjlkMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODgwIFx1YjM1NCBcdWM4MTVcdWQ2NTVcdWQ1NThcdWFjOGNcdWIyOTQsIFx1YWUzOFx1Yzc3NCA8ZW0+TjxcL2VtPlx1Yzc1OCBcdWMyMThcdWM1ZjQgPGVtPkE8XC9lbT5cdWFjMDAgXHViYWE4XHViNGUwIDEgXHVjNzc0XHVjMGMxIDxlbT5OPFwvZW0+LTImbmJzcDtcdWM3NzRcdWQ1NThcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4IDxlbT5pPFwvZW0+XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgPGVtPkE8c3ViPmk8XC9zdWI+PFwvZW0+ICZsZTsgPGVtPkE8XC9lbT48c3ViPjxlbT5pPFwvZW0+KzE8XC9zdWI+Jm5ic3A7JmxlOyA8ZW0+QTxcL2VtPjxzdWI+PGVtPmk8XC9lbT4rMjxcL3N1Yj5cdWIzYzQgXHViOWNjXHVjODcxXHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCwgPGVtPkE8c3ViPmk8XC9zdWI+PFwvZW0+ICZnZTsgPGVtPkE8XC9lbT48c3ViPjxlbT5pPFwvZW0+KzE8XC9zdWI+Jm5ic3A7JmdlOyA8ZW0+QTxcL2VtPjxzdWI+PGVtPmk8XC9lbT4rMjxcL3N1Yj5cdWIzYzQgXHViOWNjXHVjODcxXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCwgPGVtPkE8XC9lbT5cdWIyOTQgXHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzIxOFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZTM4XHVjNzc0IDxlbT5OPFwvZW0+XHVjNzU4IFx1YzIxOFx1YzVmNCA8ZW0+QTxcL2VtPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCA8ZW0+QTxcL2VtPlx1Yzc1OCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNCBcdWM5MTEgXHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhZTM4XHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG5cclxuPHA+XHVhZTM4XHVjNzc0IDxlbT5NPFwvZW0+XHVjNzU4IDxlbT5CPFwvZW0+XHVhYzAwIFx1YWUzOFx1Yzc3NCA8ZW0+TjxcL2VtPlx1Yzc3OCA8ZW0+QTxcL2VtPlx1Yzc1OCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWFjODNcdWM3NDAsIFx1YzViNFx1YjVhNCA8ZW0+aTxcL2VtPlx1YWMwMCBcdWM4NzRcdWM3YWMgXHVkNTc0XHVjMTFjLCA8ZW0+QjxcL2VtPjxzdWI+MTxcL3N1Yj4gPSA8ZW0+QTxzdWI+aTxcL3N1Yj48XC9lbT4sIDxlbT5CPFwvZW0+PHN1Yj4yPFwvc3ViPiA9IDxlbT5BPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPisxPFwvc3ViPiwmbmJzcDsuLi4sIDxlbT5CPHN1Yj5NPFwvc3ViPjxcL2VtPiA9IDxlbT5BPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPis8ZW0+TTxcL2VtPi0xPFwvc3ViPiBcdWM3NzggXHVhYzgzXHVjNzQ0IFx1YjlkMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWI0NTAgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NCA8ZW0+TjxcL2VtPlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxYyA8ZW0+TjxcL2VtPlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiA8ZW0+aTxcL2VtPlx1YmM4OFx1YzlmOCBcdWMyMThcdWIyOTQgPGVtPkE8c3ViPmk8XC9zdWI+PFwvZW0+XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD48ZW0+QTxcL2VtPlx1Yzc1OCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNCBcdWM5MTEgXHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhZTM4XHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MyAmbGU7IDxlbT5OPFwvZW0+ICZsZTsgNSwwMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IDxlbT5BPHN1Yj5pPFwvc3ViPjxcL2VtPiAmbGU7IDEwPHN1cD45PFwvc3VwPiZuYnNwOygxICZsZTsgPGVtPmk8XC9lbT4gJmxlOyA8ZW0+TjxcL2VtPik8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2sxIjoiPHA+XHVjNzc0IFx1YzExY1x1YmUwY1x1ZDBkY1x1YzJhNFx1ZDA2Y1x1YjI5NCBcdWIyZTRcdWM3NGNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC46PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+PGVtPk48XC9lbT4gPSAzPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPlx1Yzc3NCBcdWMxMWNcdWJlMGNcdWQwZGNcdWMyYTRcdWQwNmNcdWIyOTQgXHViMmU0XHVjNzRjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxlbT5OPFwvZW0+ICZsZTsgMzAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPlx1Yzc3NCBcdWMxMWNcdWJlMGNcdWQwZGNcdWMyYTRcdWQwNmNcdWIyOTQgXHVjZDk0XHVhYzAwIFx1YzgxY1x1ZDU1YyBcdWM4NzBcdWFjNzRcdWM3NzQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjE1Nzc5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiWmlnemFnIiwiZGVzY3JpcHRpb24iOiI8cD5BIHNlcXVlbmNlIGlzIGNhbGxlZCAmcXVvdDs8c3Ryb25nPlppZ3phZzxcL3N0cm9uZz4mcXVvdDsgaWYgbm8gdGhyZWUgb2YgaXRzIGNvbnNlY3V0aXZlIGVsZW1lbnRzIGFyZSBtb25vdG9uZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TW9yZSBmb3JtYWxseSwgaWYgc2VxdWVuY2UgPGVtPkE8XC9lbT4mbmJzcDtvZiBsZW5ndGggPGVtPk48XC9lbT4mbmJzcDtpcyBaaWd6YWcgaWYsIGZvciBhbGwgPGVtPmk8XC9lbT4mbmJzcDsoMSAmbGU7IDxlbT5pPFwvZW0+ICZsZTsgPGVtPk48XC9lbT4tMiksIG5laXRoZXIgPGVtPkE8c3ViPmk8XC9zdWI+PFwvZW0+ICZsZTsgPGVtPkE8XC9lbT48c3ViPjxlbT5pPFwvZW0+KzE8XC9zdWI+Jm5ic3A7JmxlOyA8ZW0+QTxcL2VtPjxzdWI+PGVtPmk8XC9lbT4rMjxcL3N1Yj4mbmJzcDtub3IgPGVtPkE8c3ViPmk8XC9zdWI+PFwvZW0+ICZnZTsgPGVtPkE8XC9lbT48c3ViPjxlbT5pPFwvZW0+KzE8XC9zdWI+Jm5ic3A7JmdlOyA8ZW0+QTxcL2VtPjxzdWI+PGVtPmk8XC9lbT4rMjxcL3N1Yj4mbmJzcDtob2xkcy48XC9wPlxyXG5cclxuPHA+Rm9yIGdpdmVuIHNlcXVlbmNlIDxlbT5BPFwvZW0+Jm5ic3A7b2YgbGVuZ3RoIDxlbT5OPFwvZW0+LCB5b3Ugc2hvdWxkIGZpbmQgYSBsb25nZXN0IHN1YnNlZ21lbnQgb2YgPGVtPkE8XC9lbT4mbmJzcDt3aGljaCBpcyBhIFppZ3phZyBzZXF1ZW5jZS48XC9wPlxyXG5cclxuPHA+U2VxdWVuY2UgPGVtPkI8XC9lbT4mbmJzcDtvZiBsZW5ndGggPGVtPk08XC9lbT4mbmJzcDtpcyBzdWJzZWdtZW50IG9mIHNlcXVlbmNlIDxlbT5BPFwvZW0+Jm5ic3A7b2YgbGVuZ3RoIDxlbT5OPFwvZW0+Jm5ic3A7aWYsIGZvciBzb21lIDxlbT5pPFwvZW0+LCA8ZW0+QjxcL2VtPjxzdWI+MTxcL3N1Yj4gPSA8ZW0+QTxzdWI+aTxcL3N1Yj48XC9lbT4sIDxlbT5CPFwvZW0+PHN1Yj4yPFwvc3ViPiA9IDxlbT5BPFwvZW0+PHN1Yj48ZW0+aTxcL2VtPisxPFwvc3ViPiwuLi4gLCA8ZW0+QjxzdWI+TTxcL3N1Yj48XC9lbT4gPSA8ZW0+QTxcL2VtPjxzdWI+PGVtPmk8XC9lbT4rPGVtPk08XC9lbT4tMTxcL3N1Yj4mbmJzcDtob2xkcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IGNvbnNpc3RzIG9mIHR3byBsaW5lcy48XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgaW50ZWdlciA8ZW0+TjxcL2VtPiwgbGVuZ3RoIG9mIHNlcXVlbmNlIDxlbT5BPFwvZW0+LjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgc3BhY2Utc2VwYXJhdGVkIDxlbT5OPFwvZW0+Jm5ic3A7aW50ZWdlcnMuIDxlbT5pPFwvZW0+dGggbnVtYmVyIGlzIDxlbT5BPHN1Yj5pPFwvc3ViPjxcL2VtPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCBvdXQgdGhlIGxlbmd0aCBvZiBsb25nZXN0IHN1YnNlZ21lbnQgb2YgPGVtPkE8XC9lbT4mbmJzcDt3aGljaCBpcyBhIFppZ3phZyBzZXF1ZW5jZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjMgJmxlOyA8ZW0+TjxcL2VtPiAmbGU7IDUsMDAwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyA8ZW0+QTxzdWI+aTxcL3N1Yj48XC9lbT4gJmxlOyAxMDxzdXA+OTxcL3N1cD4mbmJzcDsoMSAmbGU7IDxlbT5pPFwvZW0+ICZsZTsgPGVtPk48XC9lbT4pPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPlRoaXMgc3VidGFzayBoYXMgYWRkaXRpb25hbCBjb25zdHJhaW50cy46Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+PGVtPk48XC9lbT4gPSAzPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPlRoaXMgc3VidGFzayBoYXMgYWRkaXRpb25hbCBjb25zdHJhaW50cy46PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+PGVtPk48XC9lbT4gJmxlOyAzMDA8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2szIjoiPHA+VGhpcyBzdWJ0YXNrIGhhcyBubyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzLjxcL3A+XHJcbiJ9XQ==