(追記) (追記ここまで)

31719번 - UDP 스택 다국어

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	1024 MB	665	187	155	30.452%

문제

UDP 마을에는 세 개의 신비한 스택이 있다. 이를 차례로 U스택, D스택, P스택이라 하자. 이 스택들은 특별해서 스택의 바닥을 열고 닫을 수 있다. 바닥이 열려 있는 스택에 원소를 삽입하면 그 즉시 바닥 아래로 떨어지며, 바닥이 닫혀 있는 스택의 바닥을 열면 저장되어 있던 원소들이 모두 바닥 아래로 떨어진다. 이때, 스택의 바닥에 가까운 쪽의 원소들이 더 먼저 바닥으로 떨어진다. 초기에는 U스택의 바닥만이 열려 있으며, D스택과 P스택의 바닥은 닫혀 있다.

어느 날, UDP 마을에서 길이가 $N$인 순열 $A$가 발견되었다. 포닉스는 다음 두 연산만을 사용할 수 있다.

순열 $A$의 가장 앞 원소를 세 스택 중 하나에 삽입한 후 순열에서 삭제한다. 단, 이 연산은 순열 $A$가 비어있지 않을 때만 가능하다.
현재 바닥이 열려 있는 스택을 닫은 후 바닥이 닫혀 있는 스택 중 하나를 골라 연다.

포닉스는 순열 $A$와 세 스택이 모두 빌 때까지 연산을 반복한 후, 먼저 떨어진 것이 앞에 오도록 원소들을 나열할 것이다. 포닉스가 원소들을 오름차순으로 재배열할 수 있을지 판별하여라.

입력

첫째 줄에 테스트케이스의 개수 $T$가 주어진다. $(1 \le T \le 500\ 000)$

각 테스트케이스의 첫째 줄에 순열의 길이 $N$이 주어진다. $(1 \le N \le 200\ 000)$

각 테스트케이스의 둘째 줄에 순열 $A$의 원소 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $A_i$는 1ドル$ 이상 $N$ 이하의 서로 다른 정수이다.

모든 테스트케이스에 대해 $N$의 합이 500ドル\ 000$ 이하임이 보장된다.

출력

각 테스트케이스에 대해 포닉스가 원소들을 오름차순으로 재배열하는 것이 가능하면 YES, 아니면 NO를 한 줄에 하나씩 순서대로 출력하여라.

제한

예제 입력 1

예제 출력 1

YES
YES
NO

힌트

W3sicHJvYmxlbV9pZCI6IjMxNzE5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiVURQIFx1YzJhNFx1ZDBkZCIsImRlc2NyaXB0aW9uIjoiPHA+VURQIFx1YjljOFx1Yzc0NFx1YzVkMFx1YjI5NCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzJlMFx1YmU0NFx1ZDU1YyBcdWMyYTRcdWQwZGRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI5N2MgXHVjYzI4XHViODQwXHViODVjIFVcdWMyYTRcdWQwZGQsIERcdWMyYTRcdWQwZGQsIFBcdWMyYTRcdWQwZGRcdWM3NzRcdWI3N2MgXHVkNTU4XHVjNzkwLiBcdWM3NzQgXHVjMmE0XHVkMGRkXHViNGU0XHVjNzQwIFx1ZDJiOVx1YmNjNFx1ZDU3NFx1YzExYyBcdWMyYTRcdWQwZGRcdWM3NTggXHViYzE0XHViMmU1XHVjNzQ0IFx1YzVmNFx1YWNlMCBcdWIyZWJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViYzE0XHViMmU1XHVjNzc0IFx1YzVmNFx1YjgyNCBcdWM3ODhcdWIyOTQgXHVjMmE0XHVkMGRkXHVjNWQwIFx1YzZkMFx1YzE4Y1x1Yjk3YyBcdWMwYmRcdWM3ODVcdWQ1NThcdWJhNzQgXHVhZGY4IFx1Yzk4OVx1YzJkYyBcdWJjMTRcdWIyZTUgXHVjNTQ0XHViNzk4XHViODVjIFx1YjVhOFx1YzViNFx1YzljMFx1YmE3MCwgXHViYzE0XHViMmU1XHVjNzc0IFx1YjJlYlx1ZDYwMCBcdWM3ODhcdWIyOTQgXHVjMmE0XHVkMGRkXHVjNzU4IFx1YmMxNFx1YjJlNVx1Yzc0NCBcdWM1ZjRcdWJhNzQgXHVjODAwXHVjN2E1XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjM1OCBcdWM2ZDBcdWMxOGNcdWI0ZTRcdWM3NzQgXHViYWE4XHViNDUwIFx1YmMxNFx1YjJlNSBcdWM1NDRcdWI3OThcdWI4NWMgXHViNWE4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzJhNFx1ZDBkZFx1Yzc1OCBcdWJjMTRcdWIyZTVcdWM1ZDAgXHVhYzAwXHVhZTRjXHVjNmI0IFx1Y2FiZFx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWI0ZTRcdWM3NzQgXHViMzU0IFx1YmEzY1x1YzgwMCBcdWJjMTRcdWIyZTVcdWM3M2NcdWI4NWMgXHViNWE4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWNkMDhcdWFlMzBcdWM1ZDBcdWIyOTQgVVx1YzJhNFx1ZDBkZFx1Yzc1OCBcdWJjMTRcdWIyZTVcdWI5Y2NcdWM3NzQgXHVjNWY0XHViODI0IFx1Yzc4OFx1YzczY1x1YmE3MCwgRFx1YzJhNFx1ZDBkZFx1YWNmYyBQXHVjMmE0XHVkMGRkXHVjNzU4IFx1YmMxNFx1YjJlNVx1Yzc0MCBcdWIyZWJcdWQ2MDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWIyOTAgXHViMGEwLCBVRFAgXHViOWM4XHVjNzQ0XHVjNWQwXHVjMTFjIFx1YWUzOFx1Yzc3NFx1YWMwMCAkTiRcdWM3NzggXHVjMjFjXHVjNWY0ICRBJFx1YWMwMCBcdWJjMWNcdWFjYWNcdWI0MThcdWM1YzhcdWIyZTQuIFx1ZDNlY1x1YjJjOVx1YzJhNFx1YjI5NCBcdWIyZTRcdWM3NGMgXHViNDUwIFx1YzVmMFx1YzBiMFx1YjljY1x1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWMyMWNcdWM1ZjQgJEEkXHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM1NWUgXHVjNmQwXHVjMThjXHViOTdjIFx1YzEzOCBcdWMyYTRcdWQwZGQgXHVjOTExIFx1ZDU1OFx1YjA5OFx1YzVkMCBcdWMwYmRcdWM3ODVcdWQ1NWMgXHVkNmM0IFx1YzIxY1x1YzVmNFx1YzVkMFx1YzExYyBcdWMwYWRcdWM4MWNcdWQ1NWNcdWIyZTQuIFx1YjJlOCwgXHVjNzc0IFx1YzVmMFx1YzBiMFx1Yzc0MCBcdWMyMWNcdWM1ZjQgJEEkXHVhYzAwIFx1YmU0NFx1YzViNFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDQgXHViNTRjXHViOWNjIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVkNjA0XHVjN2FjIFx1YmMxNFx1YjJlNVx1Yzc3NCBcdWM1ZjRcdWI4MjQgXHVjNzg4XHViMjk0IFx1YzJhNFx1ZDBkZFx1Yzc0NCBcdWIyZWJcdWM3NDAgXHVkNmM0IFx1YmMxNFx1YjJlNVx1Yzc3NCBcdWIyZWJcdWQ2MDAgXHVjNzg4XHViMjk0IFx1YzJhNFx1ZDBkZCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YWNlOFx1Yjc3YyBcdWM1ZjBcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVkM2VjXHViMmM5XHVjMmE0XHViMjk0IFx1YzIxY1x1YzVmNCAkQSRcdWM2NDAgXHVjMTM4IFx1YzJhNFx1ZDBkZFx1Yzc3NCBcdWJhYThcdWI0NTAgXHViZTRjIFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWM1ZjBcdWMwYjBcdWM3NDQgXHViYzE4XHViY2Y1XHVkNTVjIFx1ZDZjNCwgXHViYTNjXHVjODAwIFx1YjVhOFx1YzViNFx1YzljNCBcdWFjODNcdWM3NzQgXHVjNTVlXHVjNWQwIFx1YzYyNFx1YjNjNFx1Yjg1ZCBcdWM2ZDBcdWMxOGNcdWI0ZTRcdWM3NDQgXHViMDk4XHVjNWY0XHVkNTYwIFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVkM2VjXHViMmM5XHVjMmE0XHVhYzAwIFx1YzZkMFx1YzE4Y1x1YjRlNFx1Yzc0NCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjN2FjXHViYzMwXHVjNWY0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3NDRcdWM5YzAgXHVkMzEwXHViY2M0XHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4ICRUJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMSBcXGxlIFQgXFxsZSA1MDBcXCAwMDApJDxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMjFjXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NCAkTiRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDEgXFxsZSBOIFxcbGUgMjAwXFwgMDAwKSQ8XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzIxY1x1YzVmNCAkQSRcdWM3NTggXHVjNmQwXHVjMThjICRBXzEsIEFfMiwgXFxjZG90cywgQV9OJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJEFfaSRcdWIyOTQgJDEkIFx1Yzc3NFx1YzBjMSAkTiQgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCAkTiRcdWM3NTggXHVkNTY5XHVjNzc0ICQ1MDBcXCAwMDAkIFx1Yzc3NFx1ZDU1OFx1Yzc4NFx1Yzc3NCBcdWJjZjRcdWM3YTVcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVkM2VjXHViMmM5XHVjMmE0XHVhYzAwIFx1YzZkMFx1YzE4Y1x1YjRlNFx1Yzc0NCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjN2FjXHViYzMwXHVjNWY0XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWJhNzQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPllFUzxcL2NvZGU+PFwvc3Bhbj4sIFx1YzU0NFx1YjJjOFx1YmE3NCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+Tk88XC9jb2RlPjxcL3NwYW4+XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzE3MTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJVRFAgU3RhY2siLCJkZXNjcmlwdGlvbiI6IjxwPkluIHRoZSBVRFAgdG93biwgdGhlcmUgYXJlIHRocmVlIG15c3RlcmlvdXMgc3RhY2tzLiBMZXQmIzM5O3MgY2FsbCB0aGVtIFUtc3RhY2ssIEQtc3RhY2ssIGFuZCBQLXN0YWNrIHJlc3BlY3RpdmVseS4gVGhlIHN0YWNrcyBhcmUgc3BlY2lhbCZuYnNwO2JlY2F1c2UgdGhlIGJvdHRvbSBjYW4gYmUgb3BlbmVkIGFuZCBjbG9zZWQuIFdoZW4gYW4gZWxlbWVudCBpcyBpbnNlcnRlZCBpbnRvIGEgc3RhY2sgd2hvc2UgYm90dG9tIGlzIG9wZW4sIGl0IGltbWVkaWF0ZWx5IGZhbGxzIHRocm91Z2ggdGhlIGJvdHRvbSwgYW5kIGlmIHRoZSBib3R0b20gb2YgYSBjbG9zZWQgc3RhY2sgaXMgb3BlbmVkLCBhbGwgdGhlIGVsZW1lbnRzIHN0b3JlZCBpbiBpdCBmYWxsIHRocm91Z2gmbmJzcDt0aGUgYm90dG9tLiZuYnNwO0luIHRoaXMgcHJvY2VzcywgdGhlIGVsZW1lbnRzIGNsb3NlciB0byB0aGUgYm90dG9tIG9mIHRoZSBzdGFjayBmYWxsIGZpcnN0LiBJbml0aWFsbHksIG9ubHkgdGhlIGJvdHRvbSBvZiB0aGUgVS1zdGFjayBpcyBvcGVuLCBhbmQgdGhlIGJvdHRvbXMgb2YgdGhlIEQtc3RhY2sgYW5kIFAtc3RhY2sgYXJlIGNsb3NlZC48XC9wPlxyXG5cclxuPHA+T25lIGRheSwgaW4gdGhlIFVEUCB0b3duLCBhIHBlcm11dGF0aW9uICRBJCBvZiBsZW5ndGggJE4kIHdhcyBkaXNjb3ZlcmVkLiBQb25peCBjYW4gb25seSB1c2UgdGhlIGZvbGxvd2luZyB0d28gb3BlcmF0aW9uczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5JbnNlcnQgdGhlIGZpcnN0IGVsZW1lbnQgb2YgcGVybXV0YXRpb24gJEEkIGludG8gb25lIG9mIHRoZSB0aHJlZSBzdGFja3MgYW5kIHRoZW4gZGVsZXRlIGl0IGZyb20gdGhlIHBlcm11dGF0aW9uLiZuYnNwO0hvd2V2ZXIsIHRoaXMgb3BlcmF0aW9uIGlzIG9ubHkgcG9zc2libGUgd2hlbiBwZXJtdXRhdGlvbiAkQSQgaXMgbm90IGVtcHR5LjxcL2xpPlxyXG5cdDxsaT5DbG9zZSB0aGUgY3VycmVudGx5IG9wZW4gc3RhY2smIzM5O3MgYm90dG9tLCB0aGVuIG9wZW4gb25lIG9mIHRoZSBjbG9zZWQgc3RhY2tzJiMzOTsmbmJzcDtib3R0b20uPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+UG9uaXggd2lsbCBhcnJhbmdlIGluIGEgcm93Jm5ic3A7dGhlIGVsZW1lbnRzIHN1Y2ggdGhhdCB0aGUgZmlyc3QgZWxlbWVudCB0byBmYWxsIHdpbGwgYmUgcG9zaXRpb25lZCBhdCB0aGUgZnJvbnQsIGFmdGVyIHJlcGVhdGluZyBvcGVyYXRpb25zIHVudGlsIHBlcm11dGF0aW9uICRBJCBhbmQgYWxsIHRocmVlIHN0YWNrcyBhcmUgZW1wdHkuIERldGVybWluZSBpZiBQb25peCBjYW4gcmVhcnJhbmdlIHRoZSBlbGVtZW50cyBpbiBhc2NlbmRpbmcgb3JkZXIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIHRlc3QgY29uc2lzdHMgb2YgbXVsdGlwbGUgdGVzdCBjYXNlcy4gVGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciAkVCQsIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gJCgxIFxcbGUgVCBcXGxlIDUwMFxcIDAwMCkkPFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgJE4kLCB0aGUgbGVuZ3RoIG9mIHRoZSBwZXJtdXRhdGlvbi4gJCgxIFxcbGUgTiBcXGxlIDIwMFxcIDAwMCkkPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyAkTiQgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzICRBXzEsIEFfMiwgXFxjZG90cywgQV9OJC4gRWFjaCAkQV9pJCBpcyBhIGRpc3RpbmN0IGludGVnZXImbmJzcDtmcm9tICQxJCB0byAkTiQsIGluY2x1c2l2ZS48XC9wPlxyXG5cclxuPHA+SXQgaXMgZ3VhcmFudGVlZCB0aGF0IHRoZSBzdW0gb2YgdGhlIHZhbHVlcyBvZiAkTiQgZm9yIGFsbCB0ZXN0IGNhc2VzIGRvZXMgbm90IGV4Y2VlZCAkNTAwXFwgMDAwJC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5ZRVM8XC9jb2RlPjxcL3NwYW4+IGlmIFBvbml4IGNhbiByZWFycmFuZ2UgdGhlIGVsZW1lbnRzIGluJm5ic3A7YXNjZW5kaW5nIG9yZGVyLCBhbmQgPGNvZGU+PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPk5PPFwvc3Bhbj48XC9jb2RlPiBvdGhlcndpc2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==