시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 242 89 70 40.000%

문제

정수가 저장된 크기 N인 배열 A가 있을 때, ‘순서 섞기’ 연산은 아래와 같이 정의된다.

  1. 크기가 N인 배열 B를 이용하여, 배열 A의 좌측 끝 또는 우측 끝에 있는 값 중 하나를 차례로 꺼내어 배열 B에 좌측부터 순서대로 저장한다. 아래의 그림에서 값이 꺼내지는 순서는 9, 34, 19, 12, 25, 4, 5, 36이다.
  2. 배열 B를 배열 A에 복사한다.

위에서 보인 그림처럼 순서 섞기 연산을 하면 배열 A의 값은 다음과 같이 변경된다.

(34, 19, 5, 36, 4, 25, 12, 9) =⇒ (9, 34, 19, 12, 25, 4, 5, 36)

배열 A의 i번째 원소를 Ai라고 나타내자. “1 ≤ i < j ≤ N이면 Ai ≤ Aj이다.”가 성립할 때, “배열 A는 단조증가한다”라고 말한다.

정수가 저장된 크기 N인 배열 A가 주어질 때, 배열 A가 단조증가하도록 정렬하기 위해 필요한 ‘순서 섞기’ 연산의 최소 횟수를 계산하는 프로그램을 작성하시오.

입력

첫 번째 줄에 정수 N이 주어진다.

두 번째 줄에 배열 A에 저장된 N개의 정수 A1, ..., AN이 공백을 사이에 두고 차례대로 주어진다.

출력

배열 A가 단조증가하도록 정렬하기 위해 필요한 ‘순서 섞기’ 연산의 최소 횟수를 출력한다.

제한

  • 1 ≤ N ≤ 300 000
  • 1 ≤ Ai ≤ 109

서브태스크

번호 배점 제한
1 4

N ≤ 8

2 9

답이 2 이하

3 22

Ai ≤ 2

4 18

모든 Ai가 서로 다름

5 47

추가 제약 조건 없음

예제 입력 1

3
2 2 5

예제 출력 1

0

예제 입력 2

6
1 5 8 10 3 2

예제 출력 2

1
W3sicHJvYmxlbV9pZCI6IjIwMTkyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMjFjXHVjMTFjIFx1YzExZVx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjODE1XHVjMjE4XHVhYzAwIFx1YzgwMFx1YzdhNVx1YjQxYyBcdWQwNmNcdWFlMzAgTlx1Yzc3OCBcdWJjMzBcdWM1ZjQgQVx1YWMwMCBcdWM3ODhcdWM3NDQgXHViNTRjLCAmbHNxdW87XHVjMjFjXHVjMTFjIFx1YzExZVx1YWUzMCZyc3F1bzsgXHVjNWYwXHVjMGIwXHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1ZDA2Y1x1YWUzMFx1YWMwMCBOXHVjNzc4IFx1YmMzMFx1YzVmNCBCXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYywgXHViYzMwXHVjNWY0IEFcdWM3NTggXHVjODhjXHVjZTIxIFx1YjA1ZCBcdWI2MTBcdWIyOTQgXHVjNmIwXHVjZTIxIFx1YjA1ZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhYzEyIFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjYzI4XHViODQwXHViODVjIFx1YWViY1x1YjBiNFx1YzViNCBcdWJjMzBcdWM1ZjQgQlx1YzVkMCBcdWM4OGNcdWNlMjFcdWJkODBcdWQxMzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzgwMFx1YzdhNVx1ZDU1Y1x1YjJlNC4gXHVjNTQ0XHViNzk4XHVjNzU4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWFjMTJcdWM3NzQgXHVhZWJjXHViMGI0XHVjOWMwXHViMjk0IFx1YzIxY1x1YzExY1x1YjI5NCA5LCAzNCwgMTksIDEyLCAyNSwgNCwgNSwgMzZcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmMzMFx1YzVmNCBCXHViOTdjIFx1YmMzMFx1YzVmNCBBXHVjNWQwIFx1YmNmNVx1YzBhY1x1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2Y5OTFjMTFiLTRhNGYtNGNmNS1iMGEzLTYzYjMzODBlNmU2Y1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMzU5cHg7IGhlaWdodDogMTg2cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1YzVkMFx1YzExYyBcdWJjZjRcdWM3NzggXHVhZGY4XHViOWJjXHVjYzk4XHViN2ZjIFx1YzIxY1x1YzExYyBcdWMxMWVcdWFlMzAgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1ZDU1OFx1YmE3NCBcdWJjMzBcdWM1ZjQgQVx1Yzc1OCBcdWFjMTJcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWJjYzBcdWFjYmRcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPigzNCwgMTksIDUsIDM2LCA0LCAyNSwgMTIsIDkpID0mckFycjsgKDksIDM0LCAxOSwgMTIsIDI1LCA0LCA1LCAzNik8XC9wPlxyXG5cclxuPHA+XHViYzMwXHVjNWY0IEFcdWM3NTggaVx1YmM4OFx1YzlmOCBcdWM2ZDBcdWMxOGNcdWI5N2MgQTxzdWI+aTxcL3N1Yj5cdWI3N2NcdWFjZTAgXHViMDk4XHVkMGMwXHViMGI0XHVjNzkwLiAmbGRxdW87MSAmbGU7IGkgJmx0OyBqICZsZTsgTlx1Yzc3NFx1YmE3NCBBPHN1Yj5pPFwvc3ViPiAmbGU7IEE8c3ViPmo8XC9zdWI+XHVjNzc0XHViMmU0LiZyZHF1bztcdWFjMDAgXHVjMTMxXHViOWJkXHVkNTYwIFx1YjU0YywgJmxkcXVvO1x1YmMzMFx1YzVmNCBBXHViMjk0IFx1YjJlOFx1Yzg3MFx1Yzk5ZFx1YWMwMFx1ZDU1Y1x1YjJlNCZyZHF1bztcdWI3N2NcdWFjZTAgXHViOWQwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWMyMThcdWFjMDAgXHVjODAwXHVjN2E1XHViNDFjIFx1ZDA2Y1x1YWUzMCBOXHVjNzc4IFx1YmMzMFx1YzVmNCBBXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsIFx1YmMzMFx1YzVmNCBBXHVhYzAwIFx1YjJlOFx1Yzg3MFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWM4MTVcdWI4MmNcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyAmbHNxdW87XHVjMjFjXHVjMTFjIFx1YzExZVx1YWUzMCZyc3F1bzsgXHVjNWYwXHVjMGIwXHVjNzU4IDxzdHJvbmc+XHVjZDVjXHVjMThjIFx1ZDY5Zlx1YzIxODxcL3N0cm9uZz5cdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmMzMFx1YzVmNCBBXHVjNWQwIFx1YzgwMFx1YzdhNVx1YjQxYyBOXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBBPHN1Yj4xPFwvc3ViPiwgLi4uLCBBPHN1Yj5OPFwvc3ViPlx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmMzMFx1YzVmNCBBXHVhYzAwIFx1YjJlOFx1Yzg3MFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWM4MTVcdWI4MmNcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyAmbHNxdW87XHVjMjFjXHVjMTFjIFx1YzExZVx1YWUzMCZyc3F1bzsgXHVjNWYwXHVjMGIwXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgTiAmbGU7IDMwMCAwMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IEE8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjk8XC9zdXA+PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPk4gJmxlOyA4PFwvcD5cclxuIiwic3VidGFzazIiOiI8cD5cdWIyZjVcdWM3NzQgMiBcdWM3NzRcdWQ1NTg8XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPkE8c3ViPmk8XC9zdWI+ICZsZTsgMjxcL3A+XHJcbiIsInN1YnRhc2s0IjoiPHA+XHViYWE4XHViNGUwIEE8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5ODQ8XC9wPlxyXG4iLCJzdWJ0YXNrNSI6IjxwPlx1Y2Q5NFx1YWMwMCBcdWM4MWNcdWM1N2QgXHVjODcwXHVhYzc0IFx1YzVjNlx1Yzc0YzxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjIwMTkyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSW50ZWdlciBBcnJheSBTaHVmZmxlIiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiBhbiBpbnRlZ2VyIGFycmF5ICRBJCBvZiBzaXplICROJCwgdGhlIDxlbT5zaHVmZmxlPFwvZW0+IG9wZXJhdGlvbiBpcyBkZWZpbmVkIGFzIGZvbGxvd3MuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+SW5pdGlhbGx5LCB5b3UgY3JlYXRlIGFuIGVtcHR5IGludGVnZXIgYXJyYXkgJEIkLjxcL2xpPlxyXG5cdDxsaT5UaGVuLCB3aGlsZSAkQSQgaXMgbm90IGVtcHR5LCB5b3UgcmVtb3ZlIGVpdGhlciB0aGUgbGVmdG1vc3Qgb3IgcmlnaHRtb3N0IGVsZW1lbnQgb2YgJEEkLCBhbmQgYXBwZW5kIHRoZSB2YWx1ZSB0byB0aGUgcmlnaHQgaW4gJEIkLjxcL2xpPlxyXG5cdDxsaT5JZiAkQSQgaXMgZW1wdHksIHJlcGxhY2UgJEEkIHdpdGggJEIkIGFuZCBzdG9wLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZjk5MWMxMWItNGE0Zi00Y2Y1LWIwYTMtNjNiMzM4MGU2ZTZjXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAzNTlweDsgaGVpZ2h0OiAxODZweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+SWYgdGhlIHNodWZmbGUgb3BlcmF0aW9uIGlzIHBlcmZvcm1lZCBhcyBzaG93biBpbiB0aGUgcGljdHVyZSBhYm92ZSwgdGhlIHZhbHVlIG9mIHRoZSBhcnJheSAkQSQgaXMgY2hhbmdlZCBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48cD4kJCgzNCxcXCwgMTksXFwsIDUsXFwsIDM2LFxcLCA0LFxcLCAyNSxcXCwgMTIsXFwsIDkpIFxcdG8gKDksXFwsIDM0LFxcLCAxOSxcXCwgMTIsXFwsIDI1LFxcLCA0LFxcLCA1LFxcLCAzNilcXHRleHR7Ln0kJDxcL3A+XHJcblxyXG48cD5MZXQgJEFfaSQgYmUgdGhlICRpJC10aCBlbGVtZW50IG9mIGFycmF5ICRBJC4gV2hlbiB0aGUgY29uZGl0aW9uICZxdW90O2lmICQxIFxcbGUgaSAmbHQ7IGogXFxsZSBOJCwgdGhlbiAkQV9pIFxcbGUgQV9qJCZxdW90OyBpcyBlc3RhYmxpc2hlZCwgaXQgaXMgc2FpZCB0aGF0IGFycmF5ICRBJCBpbmNyZWFzZXMgbW9ub3RvbmljYWxseS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIGFuIGludGVnZXIgYXJyYXkgJEEkIG9mIHNpemUgJE4kLCBjYWxjdWxhdGVzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBzaHVmZmxlIG9wZXJhdGlvbnMgcmVxdWlyZWQgdG8gbWFrZSB0aGUgYXJyYXkgJEEkIG1vbm90b25pY2FsbHkgaW5jcmVhc2luZy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIG9uZSBpbnRlZ2VyICROJCwgdGhlIG51bWJlciBvZiBlbGVtZW50cyBpbiBhcnJheSAkQSQgKCQxIFxcbGUgTiBcXGxlIDMgXFxjZG90IDEwXjUkKS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zICROJCBpbnRlZ2VycyAkQV8xLCBcXGxkb3RzLCBBX04kOiB0aGUgaW5pdGlhbCB2YWx1ZXMgb2YgZWxlbWVudHMgb2YgYXJyYXkgJEEkICgkMSBcXGxlIEFfaSBcXGxlIDEwXjkkKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHNodWZmbGUgb3BlcmF0aW9ucyByZXF1aXJlZCB0byBtYWtlIHRoZSBhcnJheSAkQSQgbW9ub3RvbmljYWxseSBpbmNyZWFzaW5nLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJzdWJ0YXNrMSI6IiIsInN1YnRhc2syIjoiIiwic3VidGFzazMiOiIiLCJzdWJ0YXNrNCI6IiIsInN1YnRhc2s1IjoiIn1d

채점 및 기타 정보

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