시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 332 169 143 52.768%

문제

알고리즘 수업을 듣고 감명받은 윤이는 자신만의 정렬 알고리즘을 만들기로 했다. 윤이가 만든 정렬 알고리즘 "트리플 소트"는 다음과 같이 동작한다.

  • 배열에서 연속한 위치에 있는 세 원소를 임의로 고른다.
  • 세 원소의 순서를 뒤집는다. 예를 들어 세 원소가 순서대로 $a, b, c$이면 뒤집은 뒤에는 $c,b,a$가 된다.
  • 배열이 오름차순으로 정렬될 때까지 위 과정을 반복한다.

하지만 윤이는 트리플 소트로 모든 배열을 정렬할 수 없다는 사실을 깨닫고 실망했다. $1$부터 $N$까지의 정수가 한 번씩 등장하는 배열이 주어졌을 때, 트리플 소트로 정렬할 수 있는지 판별하는 프로그램을 작성하시오.

입력

첫 번째 줄에 배열의 크기를 나타내는 정수 $N$이 주어진다.

두 번째 줄에 배열의 원소가 공백을 사이에 두고 순서대로 주어진다.

출력

트리플 소트로 주어진 배열을 오름차순으로 정렬할 수 있으면 YES, 그렇지 않으면 NO를 출력한다.

제한

$3\leq N \leq 300,000$

$1$ 이상 $N$ 이하의 정수가 주어진 배열에 한 번씩 등장한다.

서브태스크 1 (10점)

$N$은 $3, 4, 5$ 중 하나이다.

서브태스크 2 (90점)

추가적인 제약 조건이 없다.

예제 입력 1

5
1 4 5 2 3

예제 출력 1

YES

다음과 같이 트리플 소트를 통해 배열을 정렬할 수 있다.

  • $2, 3, 4$번째 원소의 순서를 뒤집으면 배열은 $[1, 2, 5, 4, 3]$이 된다.
  • $3, 4, 5$번째 원소의 순서를 뒤집으면 배열은 $[1, 2, 3, 4, 5]$가 된다. 배열이 오름차순으로 정렬되었으므로 알고리즘을 종료한다.

예제 입력 2

5
3 1 5 2 4

예제 출력 2

NO
W3sicHJvYmxlbV9pZCI6IjIwMzA5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMmI4XHViOWFjXHVkNTBjIFx1YzE4Y1x1ZDJiOCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4IFx1YzIxOFx1YzVjNVx1Yzc0NCBcdWI0ZTNcdWFjZTAgXHVhYzEwXHViYTg1XHViYzFiXHVjNzQwIFx1YzcyNFx1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWI5Y2NcdWM3NTggXHVjODE1XHViODJjIFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWM3MjRcdWM3NzRcdWFjMDAgXHViOWNjXHViNGUwIFx1YzgxNVx1YjgyYyBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OTggJnF1b3Q7XHVkMmI4XHViOWFjXHVkNTBjIFx1YzE4Y1x1ZDJiOCZxdW90O1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YjNkOVx1Yzc5MVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJjMzBcdWM1ZjRcdWM1ZDBcdWMxMWMgPHN0cm9uZz5cdWM1ZjBcdWMxOGRcdWQ1NWMgXHVjNzA0XHVjZTU4PFwvc3Ryb25nPlx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMTM4IFx1YzZkMFx1YzE4Y1x1Yjk3YyBcdWM3ODRcdWM3NThcdWI4NWMgXHVhY2UwXHViOTc4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMxMzggXHVjNmQwXHVjMThjXHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWI0YTRcdWM5ZDFcdWIyOTRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVjMTM4IFx1YzZkMFx1YzE4Y1x1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgJGEsIGIsIGMkXHVjNzc0XHViYTc0IFx1YjRhNFx1YzlkMVx1Yzc0MCBcdWI0YTRcdWM1ZDBcdWIyOTQgJGMsYixhJFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmMzMFx1YzVmNFx1Yzc3NCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjODE1XHViODJjXHViNDIwIFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWM3MDQgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1YmMxOFx1YmNmNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWQ1NThcdWM5YzBcdWI5Y2MgXHVjNzI0XHVjNzc0XHViMjk0IFx1ZDJiOFx1YjlhY1x1ZDUwYyBcdWMxOGNcdWQyYjhcdWI4NWMgXHViYWE4XHViNGUwIFx1YmMzMFx1YzVmNFx1Yzc0NCBcdWM4MTVcdWI4MmNcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YjI5NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHVhZTY4XHViMmViXHVhY2UwIFx1YzJlNFx1YjlkZFx1ZDU4OFx1YjJlNC4gJDEkXHViZDgwXHVkMTMwICROJFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHViYzMwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDJiOFx1YjlhY1x1ZDUwYyBcdWMxOGNcdWQyYjhcdWI4NWMgXHVjODE1XHViODJjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVkMzEwXHViY2M0XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjMzBcdWM1ZjRcdWM3NTggXHVkMDZjXHVhZTMwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMTggJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYzMwXHVjNWY0XHVjNzU4IFx1YzZkMFx1YzE4Y1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDJiOFx1YjlhY1x1ZDUwYyBcdWMxOGNcdWQyYjhcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YmMzMFx1YzVmNFx1Yzc0NCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjODE1XHViODJjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzQgPHNhbXA+WUVTPFwvc2FtcD4sIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgPHNhbXA+Tk88XC9zYW1wPlx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8cD4kM1xcbGVxIE4gXFxsZXEgMzAwLDAwMCQ8XC9wPlxyXG5cclxuPHA+JDEkIFx1Yzc3NFx1YzBjMSAkTiQgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViYzMwXHVjNWY0XHVjNWQwIFx1ZDU1YyBcdWJjODhcdWM1MjkgXHViNGYxXHVjN2E1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsInN1YnRhc2sxIjoiPHA+JE4kXHVjNzQwICQzLCA0LCA1JCBcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+XHVjZDk0XHVhYzAwXHVjODAxXHVjNzc4IFx1YzgxY1x1YzU3ZCBcdWM4NzBcdWFjNzRcdWM3NzQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5cdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1ZDJiOFx1YjlhY1x1ZDUwYyBcdWMxOGNcdWQyYjhcdWI5N2MgXHVkMWI1XHVkNTc0IFx1YmMzMFx1YzVmNFx1Yzc0NCBcdWM4MTVcdWI4MmNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kMiwgMywgNCRcdWJjODhcdWM5ZjggXHVjNmQwXHVjMThjXHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWI0YTRcdWM5ZDFcdWM3M2NcdWJhNzQgXHViYzMwXHVjNWY0XHVjNzQwICRbMSwgMiwgNSwgNCwgM10kXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+JDMsIDQsIDUkXHViYzg4XHVjOWY4IFx1YzZkMFx1YzE4Y1x1Yzc1OCBcdWMyMWNcdWMxMWNcdWI5N2MgXHViNGE0XHVjOWQxXHVjNzNjXHViYTc0IFx1YmMzMFx1YzVmNFx1Yzc0MCAkWzEsIDIsIDMsIDQsIDVdJFx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1YmMzMFx1YzVmNFx1Yzc3NCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjODE1XHViODJjXHViNDE4XHVjNWM4XHVjNzNjXHViYmMwXHViODVjIFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1Yzc0NCBcdWM4ODVcdWI4Y2NcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIyMDMwOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRyaXBsZSBTb3J0IiwiZGVzY3JpcHRpb24iOiI8cD5ZdW5lZSB3YXMgaW1wcmVzc2VkIGJ5IGEgcmVjZW50IGxlY3R1cmUgb24gYWxnb3JpdGhtcyBhbmQgZGVjaWRlZCB0byBkZXZpc2UgdGhlaXIgb3duIHNvcnRpbmcgYWxnb3JpdGhtLiBUaGVpciBhbGdvcml0aG0sIG5hbWVkJm5ic3A7JnF1b3Q7VHJpcGxlIFNvcnQmcXVvdDssIHdvcmtzIGFzIGZvbGxvd3MuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Rm9yIGEgZ2l2ZW4gYXJyYXksJm5ic3A7cGljayB0aHJlZSA8c3Ryb25nPmNvbnNlY3V0aXZlPFwvc3Ryb25nPiBlbGVtZW50cyBhcmJpdHJhcmlseS48XC9saT5cclxuXHQ8bGk+RmxpcCB0aGUgb3JkZXIgb2YgdGhlJm5ic3A7dGhyZWUgZWxlbWVudHMuIEZvciBleGFtcGxlLCBpZiB0aGUgY2hvc2VuIGVsZW1lbnRzIGFyZSAkYSwgYiwgYyQgaW4gdGhpcyBvcmRlciwgdGhlaXIgb3JkZXIgYmVjb21lcyAkYyxiLGEkIGFmdGVyIHRoZSBmbGlwLjxcL2xpPlxyXG5cdDxsaT5SZXBlYXQgdGhlIGFib3ZlIHR3byBzdGVwcyB1bnRpbCB0aGUgd2hvbGUgYXJyYXkgaXMgc29ydGVkLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkhvd2V2ZXIsIFl1bmVlJm5ic3A7d2FzIGRpc2FwcG9pbnRlZCB0byBmaW5kIG91dCB0aGF0IHNvbWUgYXJyYXlzIGNhbm5vdCBiZSBzb3J0ZWQgd2l0aCBUcmlwbGUgU29ydC4gR2l2ZW4gYW4gYXJyYXkgb2YgbGVuZ3RoIE4gY29uc2lzdGluZyBvZiBkaXN0aW5jdCBpbnRlZ2VycyBmcm9tICQxJCB0byAkTiQsIGRldGVybWluZSB3aGV0aGVyIHRoaXMgYXJyYXkgY2FuIGJlIHNvcnRlZCB3aXRoIFRyaXBsZSBTb3J0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciAkTiQsIGRlbm90aW5nIHRoZSBzaXplIG9mIHRoZSBhcnJheS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIHRoZSBlbGVtZW50cyBvZiB0aGUgYXJyYXkgYXMgJE4kIGludGVnZXJzLCBzZXBhcmF0ZWQgYnkmbmJzcDtzcGFjZSBjaGFyYWN0ZXJzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPklmIHRoZSBnaXZlbiBhcnJheSBjYW4gYmUgc29ydGVkIHdpdGggVHJpcGxlIFNvcnQsIHByaW50IDxzYW1wPllFUzxcL3NhbXA+LiBPdGhlcndpc2UsIHByaW50IDxzYW1wPk5PPFwvc2FtcD4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHA+JDNcXGxlcSBOIFxcbGVxIDMwMCwwMDAkPFwvcD5cclxuXHJcbjxwPkV2ZXJ5IGludGVnZXIgYmV0d2VlbiAkMSQgYW5kICROJCAoaW5jbHVzaXZlKSBhcHBlYXJzIGV4YWN0bHkgb25jZSBpbiB0aGUgYXJyYXkuPFwvcD5cclxuIiwic3VidGFzazEiOiI8cD4kTiQgaXMgZWl0aGVyICQzJCwgJDQkLCZuYnNwO29yICQ1JC48XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPk5vIGFkZGl0aW9uYWwgY29uc3RyYWludHMuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPldlIGNhbiBzb3J0IHRoaXMgYXJyYXkgdXNpbmcgVHJpcGxlIFNvcnQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+RmxpcCB0aGUgMiwgMywgYW5kIDR0aCBlbGVtZW50cy4gVGhlbiB0aGUgYXJyYXkgYmVjb21lcyAkWzEsIDIsIDUsIDQsIDNdJC48XC9saT5cclxuXHQ8bGk+RmxpcCB0aGUgMywgNCwgYW5kIDV0aCBlbGVtZW50cy4mbmJzcDtUaGVuIHRoZSBhcnJheSBiZWNvbWVzICRbMSwgMiwgMywgNCwgNV0kLiBTaW5jZSB0aGUgYXJyYXkgaXMgc29ydGVkIGluIGluY3JlYXNpbmcgb3JkZXIsIHRoZSBhbGdvcml0aG0gdGVybWluYXRlcy48XC9saT5cclxuPFwvdWw+XHJcbiJ9XQ==

채점 및 기타 정보

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