시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB2701229757.059%

문제

햄최$125$인 지훈이는 먹은 햄버거를 소화하기 위해 $60$일을 굶었다. 슬슬 배가 고픈 지훈이는 부엌에서 직접 음식을 요리해 먹기로 했다.

부엌에는 인덕션이 있고, 인덕션에 요리할 수 있는 공간이 총 세 개 있다. 그리고 공간마다 따로 있는 온도 조절 버튼 $(-,+)$으로 온도를 조절할 수 있다. 온도는 다음 규칙을 따른다.

  • 온도는 정수이며, $0$과 $9$ 사이의 값이다.
  • 처음에 모든 공간의 온도는 $0$이다.
  • $-$ / $+$를 누르면 온도가 정확히 $1$만큼 감소 / 증가한다.
  • 온도가 $0$인 상태에서 $-$를 누르면 $9$가 되고, $9$인 상태에서 $+$를 누르면 $0$이 된다.

지훈이는 인덕션으로 $N$개의 음식을 순서대로 요리할 것이고, 각 음식을 요리하려면 정확한 온도가 필요하다. 즉, 세 개의 요리 공간 중 적어도 하나는 필요한 온도로 설정되어 있어야 음식을 요리할 수 있다. 음식을 요리하는 데 걸리는 시간은 무시한다.

배가 고파 힘이 없어진 지훈이는 모든 요리를 순서대로 완성하기 위해 온도 조절 버튼을 누르는 횟수가 최대한 적었으면 한다. 각 음식을 요리하기 위해 필요한 온도가 주어질 때, 모든 요리를 순서대로 완성하기 위해 온도 조절 버튼을 눌러야 하는 최소 횟수를 알려주자!

입력

첫 번째 줄에 음식의 개수 $N$이 주어진다. $(1\leq N\leq 5\ 000)$

두 번째 줄에 각 음식을 요리하기 위해 필요한 온도를 나타내는 $N$개의 정수 $t_1,t_2,...,t_N$이 공백으로 구분되어 주어진다. $(0\leq t_i\leq 9)$

출력

모든 요리를 순서대로 완성하기 위해 온도 조절 버튼을 눌러야 하는 최소 횟수를 출력한다.

예제 입력 1

1
5

예제 출력 1

5

예제 입력 2

2
3 9

예제 출력 2

4

예제 입력 3

5
9 3 8 1 0

예제 출력 3

7
W3sicHJvYmxlbV9pZCI6IjI3OTI1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzc4XHViMzU1XHVjMTU4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1ODRcdWNkNWMkMTI1JFx1Yzc3OCBcdWM5YzBcdWQ2YzhcdWM3NzRcdWIyOTQgXHViYTM5XHVjNzQwIFx1ZDU4NFx1YmM4NFx1YWM3MFx1Yjk3YyBcdWMxOGNcdWQ2NTRcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0ICQ2MCRcdWM3N2NcdWM3NDQgXHVhZDc2XHVjNWM4XHViMmU0LiBcdWMyYWNcdWMyYWMgXHViYzMwXHVhYzAwIFx1YWNlMFx1ZDUwOCBcdWM5YzBcdWQ2YzhcdWM3NzRcdWIyOTQgXHViZDgwXHVjNWNjXHVjNWQwXHVjMTFjIFx1YzljMVx1YzgxMSBcdWM3NGNcdWMyZGRcdWM3NDQgXHVjNjk0XHViOWFjXHVkNTc0IFx1YmEzOVx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvM2VhMTFkNTItNmM2Yi00N2RiLTlkZjYtZTBkNzAzZjAzNTI1XC8tXC9wcmV2aWV3XC9cIiBcLz48XC9wPlxyXG5cclxuPHA+XHViZDgwXHVjNWNjXHVjNWQwXHViMjk0IFx1Yzc3OFx1YjM1NVx1YzE1OFx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1Yzc3OFx1YjM1NVx1YzE1OFx1YzVkMCBcdWM2OTRcdWI5YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjZjVcdWFjMDRcdWM3NzQgXHVjZDFkIFx1YzEzOCBcdWFjMWMgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhY2Y1XHVhYzA0XHViOWM4XHViMmU0IFx1YjUzMFx1Yjg1YyBcdWM3ODhcdWIyOTQgXHVjNjI4XHViM2M0IFx1Yzg3MFx1YzgwOCBcdWJjODRcdWQyYmMgJCgtLCspJFx1YzczY1x1Yjg1YyBcdWM2MjhcdWIzYzRcdWI5N2MgXHVjODcwXHVjODA4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzYyOFx1YjNjNFx1YjI5NCBcdWIyZTRcdWM3NGMgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjUzMFx1Yjk3OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM2MjhcdWIzYzRcdWIyOTQgXHVjODE1XHVjMjE4XHVjNzc0XHViYTcwLCAkMCRcdWFjZmMgJDkkIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjMTJcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWJhYThcdWI0ZTAgXHVhY2Y1XHVhYzA0XHVjNzU4IFx1YzYyOFx1YjNjNFx1YjI5NCAkMCRcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiQtJCBcLyAkKyRcdWI5N2MgXHViMjA0XHViOTc0XHViYTc0IFx1YzYyOFx1YjNjNFx1YWMwMCBcdWM4MTVcdWQ2NTVcdWQ3ODggJDEkXHViOWNjXHVkMDdjIFx1YWMxMFx1YzE4YyBcLyBcdWM5OWRcdWFjMDBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzYyOFx1YjNjNFx1YWMwMCAkMCRcdWM3NzggXHVjMGMxXHVkMGRjXHVjNWQwXHVjMTFjICQtJFx1Yjk3YyBcdWIyMDRcdWI5NzRcdWJhNzQgJDkkXHVhYzAwIFx1YjQxOFx1YWNlMCwgJDkkXHVjNzc4IFx1YzBjMVx1ZDBkY1x1YzVkMFx1YzExYyAkKyRcdWI5N2MgXHViMjA0XHViOTc0XHViYTc0ICQwJFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjOWMwXHVkNmM4XHVjNzc0XHViMjk0IFx1Yzc3OFx1YjM1NVx1YzE1OFx1YzczY1x1Yjg1YyAkTiRcdWFjMWNcdWM3NTggXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM2OTRcdWI5YWNcdWQ1NjAgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWFjMDEgXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzY5NFx1YjlhY1x1ZDU1OFx1YjgyNFx1YmE3NCBcdWM4MTVcdWQ2NTVcdWQ1NWMgXHVjNjI4XHViM2M0XHVhYzAwIFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlNC4gXHVjOTg5LCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzY5NFx1YjlhYyBcdWFjZjVcdWFjMDQgXHVjOTExIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NThcdWIwOThcdWIyOTQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzYyOFx1YjNjNFx1Yjg1YyBcdWMxMjRcdWM4MTVcdWI0MThcdWM1YjQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1Yzc0Y1x1YzJkZFx1Yzc0NCBcdWM2OTRcdWI5YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzY5NFx1YjlhY1x1ZDU1OFx1YjI5NCBcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWJiMzRcdWMyZGNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMzMFx1YWMwMCBcdWFjZTBcdWQzMGMgXHVkNzk4XHVjNzc0IFx1YzVjNlx1YzViNFx1YzljNCBcdWM5YzBcdWQ2YzhcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YzY5NFx1YjlhY1x1Yjk3YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjNjQ0XHVjMTMxXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM2MjhcdWIzYzQgXHVjODcwXHVjODA4IFx1YmM4NFx1ZDJiY1x1Yzc0NCBcdWIyMDRcdWI5NzRcdWIyOTQgXHVkNjlmXHVjMjE4XHVhYzAwIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWM4MDFcdWM1YzhcdWM3M2NcdWJhNzQgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzY5NFx1YjlhY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzYyOFx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWJhYThcdWI0ZTAgXHVjNjk0XHViOWFjXHViOTdjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM2NDRcdWMxMzFcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzYyOFx1YjNjNCBcdWM4NzBcdWM4MDggXHViYzg0XHVkMmJjXHVjNzQ0IFx1YjIwY1x1YjdlY1x1YzU3YyBcdWQ1NThcdWIyOTQgXHVjZDVjXHVjMThjIFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWM1NGNcdWI4MjRcdWM4ZmNcdWM3OTAhPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3NGNcdWMyZGRcdWM3NTggXHVhYzFjXHVjMjE4ICROJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMVxcbGVxIE5cXGxlcSA1XFwgMDAwKSQ8XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1Yzc0Y1x1YzJkZFx1Yzc0NCBcdWM2OTRcdWI5YWNcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM2MjhcdWIzYzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0ICROJFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggJHRfMSx0XzIsLi4uLHRfTiRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMFxcbGVxIHRfaVxcbGVxIDkpJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmFhOFx1YjRlMCBcdWM2OTRcdWI5YWNcdWI5N2MgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzY0NFx1YzEzMVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjNjI4XHViM2M0IFx1Yzg3MFx1YzgwOCBcdWJjODRcdWQyYmNcdWM3NDQgXHViMjBjXHViN2VjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWMxOGMgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyNzkyNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkluZHVjdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+SmVlaG9vbiwgd2hvIGlzICQxMjUkLW1hbnktYnVyZ2Vycywgc3RhcnZlZCBoaW1zZWxmIGZvciAkNjAkIGRheXMgdG8gZGlnZXN0IGEgbG90IG9mIGhhbWJ1cmdlcnMgaGUgYXRlIGxhc3QgdGltZS4gTm93IGhlIGlzIGdldHRpbmcgaHVuZ3J5LCBzbyBoZSB0cmllcyB0byBjb29rIGFuZCBlYXQgc29tZSBkaXNoZXMgaGltc2VsZiBpbiB0aGUga2l0Y2hlbi48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9mZDk1YzUyNy02ZjI1LTQ5NGYtYmUxNS0zMmFhODczZTNmYzlcLy1cL3ByZXZpZXdcL1wiIFwvPjxcL3A+XHJcblxyXG48cD5UaGVyZSBpcyBhbiBpbmR1Y3Rpb24gaW4gdGhlIGtpdGNoZW4sIGFuZCB0aGUgaW5kdWN0aW9uIGhhcyB0aHJlZSBzdG92ZXMgdGhhdCBoZSBjYW4gY29vayBvbi4gSGUgY2FuIGFkanVzdCB0aGUgdGVtcGVyYXR1cmUgb2YgYSBzdG92ZSB3aXRoIHRlbXBlcmF0dXJlIGNvbnRyb2wgYnV0dG9ucyAkKC0sKykkIGZvciBlYWNoIHN0b3ZlLiBUaGUmbmJzcDt0ZW1wZXJhdHVyZSZuYnNwO2ZvbGxvd3MgdGhlIGZvbGxvd2luZyBydWxlczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgdGVtcGVyYXR1cmUgaXMgYW4gaW50ZWdlciBiZXR3ZWVuICQwJCBhbmQgJDkkLjxcL2xpPlxyXG5cdDxsaT5Jbml0aWFsbHksIHRoZSB0ZW1wZXJhdHVyZSBvZiBldmVyeSBzdG92ZSZuYnNwO2lzICQwJC48XC9saT5cclxuXHQ8bGk+V2hlbiBoZSB0b3VjaGVzIHRoZSAkLSQgXC8gJCskIGJ1dHRvbiwgdGhlIHRlbXBlcmF0dXJlIGRlY3JlYXNlcyBcLyBpbmNyZWFzZXMgYnkgZXhhY3RseSAkMSQuPFwvbGk+XHJcblx0PGxpPklmIGhlIHRvdWNoZXMgdGhlICQtJCBidXR0b24gd2hlbiB0aGUgdGVtcGVyYXR1cmUgaXMgJDAkLCBpdCB3aWxsIGJlIHNldCB0byAkOSQuIEFsc28sIGlmIGhlIHRvdWNoZXMgdGhlICQrJCBidXR0b24gd2hlbiB0aGUgdGVtcGVyYXR1cmUgaXMgJDkkLCBpdCB3aWxsIGJlIHNldCB0byAkMCQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SGUgd2lsbCBjb29rICROJCBkaXNoZXMmbmJzcDtpbiB0aGUgZ2l2ZW4gb3JkZXIgb24gdGhlIGluZHVjdGlvbiwgYW5kIGVhY2ggZGlzaCBuZWVkcyB0byBiZSBjb29rZWQgYXQgdGhlIGNvcnJlY3QgdGVtcGVyYXR1cmUuIFRoYXQgaXMsIGEgZGlzaCBjYW4gYmUgY29va2VkIG9ubHkgd2hlbiBhdCBsZWFzdCBvbmUgb2YgdGhlIHRocmVlIHN0b3ZlcyBpcyBzZXQgdG8gdGhlIHJlcXVpcmVkIHRlbXBlcmF0dXJlLiBZb3UgbWF5IGlnbm9yZSB0aGUgdGltZSBpdCB0YWtlcyB0byBjb29rIGRpc2hlcy48XC9wPlxyXG5cclxuPHA+SGUgaGFzIGxvc3QgdGhlIGVuZXJneSB0byBtb3ZlIGZyb20gaHVuZ2VyLCBzbyBoZSB3YW50cyB0byB0b3VjaCB0aGUgdGVtcGVyYXR1cmUgY29udHJvbCBidXR0b25zIGFzIGxpdHRsZSBhcyBwb3NzaWJsZSB0byBjb29rIGFsbCBkaXNoZXMgaW4gdGhlIGdpdmVuIG9yZGVyLiBHaXZlbiB0aGUgcmVxdWlyZWQgdGVtcGVyYXR1cmUgdG8gY29vayBlYWNoIGRpc2gsIGxldCZyc3F1bztzIHRlbGwgaGltIHRoZSBtaW5pbXVtIG51bWJlciBvZiB0aW1lcyBoZSBuZWVkcyB0byB0b3VjaCB0aGUgdGVtcGVyYXR1cmUgY29udHJvbCBidXR0b25zIHRvIGNvb2sgYWxsIGRpc2hlcyZuYnNwO2luIHRoZSBnaXZlbiBvcmRlciE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGRhdGEgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciAkTiQgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIGRpc2hlcy4gJCgxXFxsZXEgTlxcbGVxIDVcXCAwMDApJDxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIGxpbmUgY29udGFpbnMgJE4kIGludGVnZXJzICR0XzEsdF8yLC4uLix0X04kICZtZGFzaDsgdGhlIHRlbXBlcmF0dXJlIHJlcXVpcmVkIHRvIGNvb2sgJGkkLXRoIGRpc2guICQoMFxcbGVxIHRfaVxcbGVxIDkpJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIGEgc2luZ2xlIGxpbmUsIHByaW50Jm5ic3A7YW4mbmJzcDtpbnRlZ2VyJm5ic3A7Jm1kYXNoOyB0aGUgbWluaW11bSBudW1iZXIgb2YgdGltZXMgaGUgbmVlZHMgdG8gdG91Y2ggdGhlIHRlbXBlcmF0dXJlIGNvbnRyb2wgYnV0dG9ucyB0byBjb29rIGFsbCB0aGUgZGlzaGVzIGluIHRoZSBnaXZlbiBvcmRlci48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d