시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 1024 MB 358 128 110 54.726%

문제

어떤 수열에서, 연속된 3개의 수를 보았을 때, 그 수가 단조증가 수열이거나, 단조감소 수열인 경우가 없으면 이 수열을 "지그재그 수열" 이라고 말한다.

좀 더 정확하게는, 길이 N의 수열 A가 모든 1 이상 N-2 이하의 자연수 i에 대해서, AiAi+1 ≤ Ai+2도 만족하지 않고, AiAi+1 ≥ Ai+2도 만족하지 않으면, A는 지그재그 수열이다.

길이 N의 수열 A가 주어졌을 때, A의 연속된 부분 수열 중 지그재그 수열의 최대 길이를 구하여라.

길이 MB가 길이 NA의 연속된 부분 수열이라는 것은, 어떤 i가 존재 해서, B1 = Ai, B2 = Ai+1, ..., BM = Ai+M-1 인 것을 말한다.

입력

입력은 두 줄로 이루어져 있다. 첫째 줄에는 수열의 길이 N이 주어진다.

둘째 줄에는 공백으로 구분된 N개의 정수가 주어진다. i번째 수는 Ai를 의미한다.

출력

A의 연속된 부분 수열 중 지그재그 수열의 최대 길이를 구하여라. 

제한

  • 3 ≤ N ≤ 5,000
  • 1 ≤ Ai ≤ 109 (1 ≤ iN)

서브태스크 1 (33점)

이 서브태스크는 다음의 조건을 만족한다.:

  • N = 3

서브태스크 2 (37점)

이 서브태스크는 다음의 조건을 만족한다.:

  • N ≤ 300

서브태스크 3 (30점)

이 서브태스크는 추가 제한 조건이 없다.

예제 입력 1

3
1 2 3

예제 출력 1

2

예제 입력 2

5
1 3 4 2 5

예제 출력 2

4
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+QTxcL2VtPlx1Yzc1OCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNCBcdWM5MTEgXHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhZTM4XHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQiLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+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+dGggbnVtYmVyIGlzIDxlbT5BPHN1Yj5pPFwvc3ViPjxcL2VtPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCBvdXQgdGhlIGxlbmd0aCBvZiBsb25nZXN0IHN1YnNlZ21lbnQgb2YgPGVtPkE8XC9lbT4mbmJzcDt3aGljaCBpcyBhIFppZ3phZyBzZXF1ZW5jZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQiLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MyAmbGU7IDxlbT5OPFwvZW0+ICZsZTsgNSwwMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IDxlbT5BPHN1Yj5pPFwvc3ViPjxcL2VtPiAmbGU7IDEwPHN1cD45PFwvc3VwPiZuYnNwOygxICZsZTsgPGVtPmk8XC9lbT4gJmxlOyA8ZW0+TjxcL2VtPik8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2sxIjoiPHA+VGhpcyBzdWJ0YXNrIGhhcyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzLjombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48ZW0+TjxcL2VtPiA9IDM8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2syIjoiPHA+VGhpcyBzdWJ0YXNrIGhhcyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzLjo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48ZW0+TjxcL2VtPiAmbGU7IDMwMDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazMiOiI8cD5UaGlzIHN1YnRhc2sgaGFzIG5vIGFkZGl0aW9uYWwgY29uc3RyYWludHMuPFwvcD5cclxuIn1d

출처

University > KAIST > 2018 KAIST RUN Spring Contest Z번

채점

  • 예제는 채점하지 않는다.