시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 215 26 21 15.909%

문제

암호문을 만드는 방법에는 여러 가지가 있는데, 보통 이를 위해서 암호화 하려는 글(혹은 파일 등)을 하나의 수열로 나타내게 된다. 이 문제에서는 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+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM3NTggXHVhYzFjXHVjMjE4IFQoMSZsZTtUJmxlOzEwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBuKDQmbGU7biZsZTs1LDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjMjhcdWI4NDBcdWI4NWMgQVsxXSwgQVsyXSwgJmhlbGxpcDssIEFbbl1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggQVtpXVx1YjI5NCAxXHVjNzc0XHVjMGMxIDEwLDAwMCBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBBW2ldXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTU4XHVjNzkwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzU3ZFx1YzgxMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgWWVzXHViOTdjLCBcdWM1NDRcdWIyY2MgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IE5vXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMjcxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiV2VhayBLZXkiLCJkZXNjcmlwdGlvbiI6IjxwPkNoZW9sc29vIGlzIGEgY3J5cHRvZ3JhcGhlciBpbiBJQ1BDKEludGVybmF0aW9uYWwgQ3J5cHRvZ3JhcGhpYyBQcm9ncmFtIENvbXBhbnkpLiBSZWNlbnRseSwgQ2hlb2xzb28gZGV2ZWxvcGVkIGEgY3J5cHRvZ3JhcGhpYyBhbGdvcml0aG0gY2FsbGVkIEFDTShBZHZhbmNlZCBDcnlwdG9ncmFwaGljIE1ldGhvZCkuIEFDTSB1c2VzIGEga2V5IHRvIGVuY3J5cHQgYSBtZXNzYWdlLiBUaGUgZW5jcnlwdGVkIG1lc3NhZ2UgaXMgY2FsbGVkIGEgY2lwaGVyIHRleHQuIEluIEFDTSwgdG8gZGVjcnlwdCBhIGNpcGhlciB0ZXh0LCB0aGUgc2FtZSBrZXkgdXNlZCBpbiB0aGUgZW5jcnlwdGlvbiBzaG91bGQgYmUgYXBwbGllZC4gVGhhdCBpcywgdGhlIGVuY3J5cHRpb24ga2V5IGFuZCB0aGUgZGVjcnlwdGlvbiBrZXkgYXJlIHRoZSBzYW1lLiBTbywgdGhlIHNlbmRlciBhbmQgcmVjZWl2ZXIgc2hvdWxkIGFncmVlIG9uIGEga2V5IGJlZm9yZSB0aGV5IGNvbW11bmljYXRlIHNlY3VyZWx5IHVzaW5nIEFDTS4gU29vbiBhZnRlciBDaGVvbHNvbyBmaW5pc2hlZCB0aGUgZGVzaWduIG9mIEFDTSwgaGUgYXNrZWQgaXRzIGFuYWx5c2lzIG9uIHNlY3VyaXR5IHRvIFlvdW5naGVlIHdobyBpcyBhIGNyeXB0YW5hbHlzdCBpbiBJQ1BDLjxcL3A+XHJcblxyXG48cD5Zb3VuZ2hlZSBoYXMgYW4gaW50ZXJlc3QgaW4gYnJlYWtpbmcgY3J5cHRvc3lzdGVtcy4gQWN0dWFsbHksIHNoZSBkZXZlbG9wZWQgbWFueSBhdHRhY2tpbmcgbWV0aG9kcyBmb3Igd2VsbC1rbm93biBjcnlwdG9ncmFwaGljIGFsZ29yaXRobXMuIFNvbWUgY3J5cHRvZ3JhcGhpYyBhbGdvcml0aG1zIGhhdmUgd2VhayBrZXlzLiBXaGVuIGEgbWVzc2FnZSBpcyBlbmNyeXB0ZWQgd2l0aCBhIHdlYWsga2V5LCB0aGUgbWVzc2FnZSBjYW4gYmUgcmVjb3ZlcmVkIGVhc2lseSB3aXRob3V0IHRoZSBrZXkgZnJvbSB0aGUgY2lwaGVyIHRleHQuIFNvLCB3ZWFrIGtleSBzaG91bGQgbm90IGJlIHVzZWQgd2hlbiBlbmNyeXB0aW5nIGEgbWVzc2FnZS4gQWZ0ZXIgbWFueSB0cmlhbHMsIHNoZSBmb3VuZCB0aGUgY2hhcmFjdGVyaXN0aWMgb2Ygd2VhayBrZXlzIGluIEFDTS4gQUNNIHVzZXMgYSBzZXF1ZW5jZSBvZiBtdXR1YWxseSBkaXN0aW5jdCBwb3NpdGl2ZSBpbnRlZ2VycyAoTjxzdWI+MTxcL3N1Yj4sIE48c3ViPjI8XC9zdWI+LCAuLi4sIE48c3ViPms8XC9zdWI+KSBhcyBhIGtleS48XC9wPlxyXG5cclxuPHA+WW91bmdoZWUgZm91bmQgdGhhdCB3ZWFrIGtleXMgaW4gQUNNIGhhdmUgdGhlIGZvbGxvd2luZyB0d28gc3BlY2lhbCBwYXR0ZXJuczo8XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIGZvdXIgaW50ZWdlcnMgTjxzdWI+cDxcL3N1Yj4sIE48c3ViPnE8XC9zdWI+LCBOPHN1Yj5yPFwvc3ViPiwgTjxzdWI+czxcL3N1Yj4gKDEgJmxlOyBwICZsdDsgcSAmbHQ7IHIgJmx0OyBzICZsZTsgaykgaW4gdGhlIGtleSBzdWNoIHRoYXQ8YnIgXC8+XHJcbigxKSBOPHN1Yj5xPFwvc3ViPiAmZ3Q7IE48c3ViPnM8XC9zdWI+ICZndDsgTjxzdWI+cDxcL3N1Yj4gJmd0OyBOPHN1Yj5yPFwvc3ViPiBvciAoMikgTjxzdWI+cTxcL3N1Yj4gJmx0OyBOPHN1Yj5zPFwvc3ViPiAmbHQ7IE48c3ViPnA8XC9zdWI+ICZsdDsgTjxzdWI+cjxcL3N1Yj48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHRoZSBrZXkgKDEwLCAzMCwgNjAsIDQwLCAyMCwgNTApIGhhcyB0aGUgcGF0dGVybiBpbiAoMSk7IChfICwgMzAsIDYwLCBfICwgMjAsIDUwKS4gU28sIHRoZSBrZXkgaXMgYSB3ZWFrIGtleSBpbiBBQ00uIEJ1dCwgdGhlIGtleSAoMzAsIDQwLCAxMCwgMjAsIDgwLCA1MCwgNjAsIDcwKSBpcyBub3Qgd2VhayBiZWNhdXNlIGl0IGRvZXMgbm90IGhhdmUgYW55IHBhdHRlcm4gaW4gdGhlIGFib3ZlLjxcL3A+XHJcblxyXG48cD5Ob3csIFlvdW5naGVlIHdhbnRzIHRvIGZpbmQgYW4gZWZmaWNpZW50IG1ldGhvZCB0byBkZXRlcm1pbmUsIGZvciBhIGdpdmVuIGtleSwgd2hldGhlciBpdCBpcyBhIHdlYWsga2V5IG9yIG5vdC4gV3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FuIGhlbHAgWW91bmdoZWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlLiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIGssIHRoZSBsZW5ndGggb2YgYSBzZXF1ZW5jZSByZXByZXNlbnRpbmcgYSBrZXksIDQgJmxlOyBrICZsZTsgNSwwMDAuIEluIHRoZSBuZXh0IGxpbmUsIGsgbXV0dWFsbHkgZGlzdGluY3QgcG9zaXRpdmUgaW50ZWdlcnMgYXJlIGdpdmVuLiBUaGVyZSBpcyBhIHNpbmdsZSBzcGFjZSBiZXR3ZWVuIHRoZSBpbnRlZ2VycywgYW5kIHRoZSBpbnRlZ2VycyBhcmUgYmV0d2VlbiAxIGFuZCAxMDAsMDAwLCBib3RoIGluY2x1c2l2ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gUHJpbnQgWUVTIGlmIHRoZSBzZXF1ZW5jZSBpcyBhIHdlYWsga2V5LiBPdGhlcndpc2UsIHByaW50IE5PLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==