시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB406644516.304%

문제

암호문을 만드는 방법에는 여러 가지가 있는데, 보통 이를 위해서 암호화 하려는 글(혹은 파일 등)을 하나의 수열로 나타내게 된다. 이 문제에서는 A[1], A[2], …, A[n]의 수열을 암호화 하려 한다고 하자.

이 수열을 암호화 하는 대단히 효율적인 알고리즘을 발견하였는데, 이 알고리즘에는 약점이 하나 있다. 바로 수열이 특정 조건을 만족할 경우에는 복호화(암호문을 다시 원래의 글로 바꾸는 것)가 유일하지 않게 된다는 점이다.

수열이 주어졌을 때, 이 수열이 우리가 사용하려는 암호화 알고리즘의 약점인지 아닌지를 판별하는 프로그램을 작성하여라.

수열이 1 ≤ p < q < r < s ≤ n 을 만족하는 p, q, r, s 에 대해서 A[q] < A[s] < A[p] < A[r]이나 A[q] > A[s] > A[p] > A[r]를 만족하는 경우가 있다면 이러한 경우가 약점이 된다. 즉, 1 ≤ p < q < r < s ≤ n 이 되도록 p, q, r, s를 어떻게 잘 선택했는데, 이때 A[q] < A[s] < A[p] < A[r]이 만족되거나, A[q] > A[s] > A[p] > A[r]이 만족되는 경우가 약점이다.

입력

첫째 줄에 데이터의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각각의 데이터의 첫째 줄에는 n(4 ≤ n ≤ 5,000)이 주어진다. 그 다음 줄에는 차례로 A[1], A[2], …, A[n]이 주어진다. 각각의 A[i]는 1이상 10,000 이하이다. 모든 A[i]는 서로 다르다.

출력

T개의 줄에 각각의 데이터에 대한 결과를 출력한다. 약점인 경우에는 Yes를, 아닌 경우에는 No를 출력한다.

예제 입력 1

3
6
10 30 60 40 20 50
8
30 40 10 20 80 50 60 70
4
1 2 20 9

예제 출력 1

Yes
No
No
W3sicHJvYmxlbV9pZCI6IjIyNzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NTRcdWQ2MzhcdWQ2NTQgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzU4IFx1YzU3ZFx1YzgxMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNTU0XHVkNjM4XHViYjM4XHVjNzQ0IFx1YjljY1x1YjRkY1x1YjI5NCBcdWJjMjlcdWJjOTVcdWM1ZDBcdWIyOTQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YmNmNFx1ZDFiNSBcdWM3NzRcdWI5N2MgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzU1NFx1ZDYzOFx1ZDY1NCBcdWQ1NThcdWI4MjRcdWIyOTQgXHVhZTAwKFx1ZDYzOVx1Yzc0MCBcdWQzMGNcdWM3N2MgXHViNGYxKVx1Yzc0NCBcdWQ1NThcdWIwOThcdWM3NTggXHVjMjE4XHVjNWY0XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWNcdWIyOTQgQVsxXSwgQVsyXSwgJmhlbGxpcDssIEFbbl1cdWM3NTggXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzU1NFx1ZDYzOFx1ZDY1NCBcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM1NTRcdWQ2MzhcdWQ2NTQgXHVkNTU4XHViMjk0IFx1YjMwMFx1YjJlOFx1ZDc4OCBcdWQ2YThcdWM3MjhcdWM4MDFcdWM3NzggXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQ0IFx1YmMxY1x1YWNhY1x1ZDU1OFx1YzYwMFx1YjI5NFx1YjM3MCwgXHVjNzc0IFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1YzVkMFx1YjI5NCBcdWM1N2RcdWM4MTBcdWM3NzQgXHVkNTU4XHViMDk4IFx1Yzc4OFx1YjJlNC4gXHViYzE0XHViODVjIFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWQyYjlcdWM4MTUgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU2MCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViY2Y1XHVkNjM4XHVkNjU0KFx1YzU1NFx1ZDYzOFx1YmIzOFx1Yzc0NCBcdWIyZTRcdWMyZGMgXHVjNmQwXHViNzk4XHVjNzU4IFx1YWUwMFx1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHVhYzgzKVx1YWMwMCBcdWM3MjBcdWM3N2NcdWQ1NThcdWM5YzAgXHVjNTRhXHVhYzhjIFx1YjQxY1x1YjJlNFx1YjI5NCBcdWM4MTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzZiMFx1YjlhY1x1YWMwMCBcdWMwYWNcdWM2YTlcdWQ1NThcdWI4MjRcdWIyOTQgXHVjNTU0XHVkNjM4XHVkNjU0IFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1Yzc1OCBcdWM1N2RcdWM4MTBcdWM3NzhcdWM5YzAgXHVjNTQ0XHViMmNjXHVjOWMwXHViOTdjIFx1ZDMxMFx1YmNjNFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWM1ZjRcdWM3NzQgMSAmbGU7IHAgJmx0OyBxICZsdDsgciAmbHQ7IHMgJmxlOyBuIFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgcCwgcSwgciwgcyBcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIEFbcV0gJmx0OyBBW3NdICZsdDsgQVtwXSAmbHQ7IEFbcl1cdWM3NzRcdWIwOTggQVtxXSAmZ3Q7IEFbc10gJmd0OyBBW3BdICZndDsgQVtyXVx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1Yzc4OFx1YjJlNFx1YmE3NCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzU3ZFx1YzgxMFx1Yzc3NCBcdWI0MWNcdWIyZTQuIFx1Yzk4OSwgMSAmbGU7IHAgJmx0OyBxICZsdDsgciAmbHQ7IHMgJmxlOyBuIFx1Yzc3NCBcdWI0MThcdWIzYzRcdWI4NWQgcCwgcSwgciwgc1x1Yjk3YyBcdWM1YjRcdWI1YmJcdWFjOGMgXHVjNzk4IFx1YzEyMFx1ZDBkZFx1ZDU4OFx1YjI5NFx1YjM3MCwgXHVjNzc0XHViNTRjIEFbcV0gJmx0OyBBW3NdICZsdDsgQVtwXSAmbHQ7IEFbcl1cdWM3NzQgXHViOWNjXHVjODcxXHViNDE4XHVhYzcwXHViMDk4LCBBW3FdICZndDsgQVtzXSAmZ3Q7IEFbcF0gJmd0OyBBW3JdXHVjNzc0IFx1YjljY1x1Yzg3MVx1YjQxOFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNTdkXHVjODEwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM3NTggXHVhYzFjXHVjMjE4IFQoMSAmbGU7IFQgJmxlOyAxMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViMzcwXHVjNzc0XHVkMTMwXHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgbig0ICZsZTsgbiAmbGU7IDUsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2MyOFx1Yjg0MFx1Yjg1YyBBWzFdLCBBWzJdLCAmaGVsbGlwOywgQVtuXVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBBW2ldXHViMjk0IDFcdWM3NzRcdWMwYzEgMTAsMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIEFbaV1cdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjMDFcdWFjMDFcdWM3NTggXHViMzcwXHVjNzc0XHVkMTMwXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWFjYjBcdWFjZmNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM1N2RcdWM4MTBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFllc1x1Yjk3YywgXHVjNTQ0XHViMmNjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBOb1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjI3MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldlYWsgS2V5IiwiZGVzY3JpcHRpb24iOiI8cD5DaGVvbHNvbyBpcyBhIGNyeXB0b2dyYXBoZXIgaW4gSUNQQyhJbnRlcm5hdGlvbmFsIENyeXB0b2dyYXBoaWMgUHJvZ3JhbSBDb21wYW55KS4gUmVjZW50bHksIENoZW9sc29vIGRldmVsb3BlZCBhIGNyeXB0b2dyYXBoaWMgYWxnb3JpdGhtIGNhbGxlZCBBQ00oQWR2YW5jZWQgQ3J5cHRvZ3JhcGhpYyBNZXRob2QpLiBBQ00gdXNlcyBhIGtleSB0byBlbmNyeXB0IGEgbWVzc2FnZS4gVGhlIGVuY3J5cHRlZCBtZXNzYWdlIGlzIGNhbGxlZCBhIGNpcGhlciB0ZXh0LiBJbiBBQ00sIHRvIGRlY3J5cHQgYSBjaXBoZXIgdGV4dCwgdGhlIHNhbWUga2V5IHVzZWQgaW4gdGhlIGVuY3J5cHRpb24gc2hvdWxkIGJlIGFwcGxpZWQuIFRoYXQgaXMsIHRoZSBlbmNyeXB0aW9uIGtleSBhbmQgdGhlIGRlY3J5cHRpb24ga2V5IGFyZSB0aGUgc2FtZS4gU28sIHRoZSBzZW5kZXIgYW5kIHJlY2VpdmVyIHNob3VsZCBhZ3JlZSBvbiBhIGtleSBiZWZvcmUgdGhleSBjb21tdW5pY2F0ZSBzZWN1cmVseSB1c2luZyBBQ00uIFNvb24gYWZ0ZXIgQ2hlb2xzb28gZmluaXNoZWQgdGhlIGRlc2lnbiBvZiBBQ00sIGhlIGFza2VkIGl0cyBhbmFseXNpcyBvbiBzZWN1cml0eSB0byBZb3VuZ2hlZSB3aG8gaXMgYSBjcnlwdGFuYWx5c3QgaW4gSUNQQy48XC9wPlxyXG5cclxuPHA+WW91bmdoZWUgaGFzIGFuIGludGVyZXN0IGluIGJyZWFraW5nIGNyeXB0b3N5c3RlbXMuIEFjdHVhbGx5LCBzaGUgZGV2ZWxvcGVkIG1hbnkgYXR0YWNraW5nIG1ldGhvZHMgZm9yIHdlbGwta25vd24gY3J5cHRvZ3JhcGhpYyBhbGdvcml0aG1zLiBTb21lIGNyeXB0b2dyYXBoaWMgYWxnb3JpdGhtcyBoYXZlIHdlYWsga2V5cy4gV2hlbiBhIG1lc3NhZ2UgaXMgZW5jcnlwdGVkIHdpdGggYSB3ZWFrIGtleSwgdGhlIG1lc3NhZ2UgY2FuIGJlIHJlY292ZXJlZCBlYXNpbHkgd2l0aG91dCB0aGUga2V5IGZyb20gdGhlIGNpcGhlciB0ZXh0LiBTbywgd2VhayBrZXkgc2hvdWxkIG5vdCBiZSB1c2VkIHdoZW4gZW5jcnlwdGluZyBhIG1lc3NhZ2UuIEFmdGVyIG1hbnkgdHJpYWxzLCBzaGUgZm91bmQgdGhlIGNoYXJhY3RlcmlzdGljIG9mIHdlYWsga2V5cyBpbiBBQ00uIEFDTSB1c2VzIGEgc2VxdWVuY2Ugb2YgbXV0dWFsbHkgZGlzdGluY3QgcG9zaXRpdmUgaW50ZWdlcnMgKE48c3ViPjE8XC9zdWI+LCBOPHN1Yj4yPFwvc3ViPiwgLi4uLCBOPHN1Yj5rPFwvc3ViPikgYXMgYSBrZXkuPFwvcD5cclxuXHJcbjxwPllvdW5naGVlIGZvdW5kIHRoYXQgd2VhayBrZXlzIGluIEFDTSBoYXZlIHRoZSBmb2xsb3dpbmcgdHdvIHNwZWNpYWwgcGF0dGVybnM6PFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSBmb3VyIGludGVnZXJzIE48c3ViPnA8XC9zdWI+LCBOPHN1Yj5xPFwvc3ViPiwgTjxzdWI+cjxcL3N1Yj4sIE48c3ViPnM8XC9zdWI+ICgxICZsZTsgcCAmbHQ7IHEgJmx0OyByICZsdDsgcyAmbGU7IGspIGluIHRoZSBrZXkgc3VjaCB0aGF0PGJyIFwvPlxyXG4oMSkgTjxzdWI+cTxcL3N1Yj4gJmd0OyBOPHN1Yj5zPFwvc3ViPiAmZ3Q7IE48c3ViPnA8XC9zdWI+ICZndDsgTjxzdWI+cjxcL3N1Yj4gb3IgKDIpIE48c3ViPnE8XC9zdWI+ICZsdDsgTjxzdWI+czxcL3N1Yj4gJmx0OyBOPHN1Yj5wPFwvc3ViPiAmbHQ7IE48c3ViPnI8XC9zdWI+PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB0aGUga2V5ICgxMCwgMzAsIDYwLCA0MCwgMjAsIDUwKSBoYXMgdGhlIHBhdHRlcm4gaW4gKDEpOyAoXyAsIDMwLCA2MCwgXyAsIDIwLCA1MCkuIFNvLCB0aGUga2V5IGlzIGEgd2VhayBrZXkgaW4gQUNNLiBCdXQsIHRoZSBrZXkgKDMwLCA0MCwgMTAsIDIwLCA4MCwgNTAsIDYwLCA3MCkgaXMgbm90IHdlYWsgYmVjYXVzZSBpdCBkb2VzIG5vdCBoYXZlIGFueSBwYXR0ZXJuIGluIHRoZSBhYm92ZS48XC9wPlxyXG5cclxuPHA+Tm93LCBZb3VuZ2hlZSB3YW50cyB0byBmaW5kIGFuIGVmZmljaWVudCBtZXRob2QgdG8gZGV0ZXJtaW5lLCBmb3IgYSBnaXZlbiBrZXksIHdoZXRoZXIgaXQgaXMgYSB3ZWFrIGtleSBvciBub3QuIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbiBoZWxwIFlvdW5naGVlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZSBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZS4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBrLCB0aGUgbGVuZ3RoIG9mIGEgc2VxdWVuY2UgcmVwcmVzZW50aW5nIGEga2V5LCA0ICZsZTsgayAmbGU7IDUsMDAwLiBJbiB0aGUgbmV4dCBsaW5lLCBrIG11dHVhbGx5IGRpc3RpbmN0IHBvc2l0aXZlIGludGVnZXJzIGFyZSBnaXZlbi4gVGhlcmUgaXMgYSBzaW5nbGUgc3BhY2UgYmV0d2VlbiB0aGUgaW50ZWdlcnMsIGFuZCB0aGUgaW50ZWdlcnMgYXJlIGJldHdlZW4gMSBhbmQgMTAwLDAwMCwgYm90aCBpbmNsdXNpdmUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFByaW50IFlFUyBpZiB0aGUgc2VxdWVuY2UgaXMgYSB3ZWFrIGtleS4gT3RoZXJ3aXNlLCBwcmludCBOTy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Seoul 2004 H번

  • 데이터를 추가한 사람: bnb2011