시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 92 44 42 76.364%

문제

다항식을 계산하기 위해 고안된 계산기가 있다. 이 계산기에는 0부터 9까지의 숫자와 +, ×(곱하기), x, =의 14개의 키가 있다.

예를 들어 이 계산기를 이용하여 x^3 + x + 11을 계산하려면 x, ×, x, ×, x, +, x + 1, 1, = 을 누르면 된다. 또 x^3 + 2x^2 + 11을 계산하기 위해서는 x, +, 2, ×, x, ×, x, +, 1, 1, = 을 누르면 된다.

일반적인 계산기라면 x, +, 2, ×, x, ×, x, +, 1, 1, = 을 x + 2x^2 + 11로 인식하겠지만, 이 계산기는 추가 메모리가 없기 때문에 계산을 할 때에 계산 직전에 계산기에 저장되어 있던 값에 계산을 한다. 즉 x, +, 2, ×, x, ×, x, +, 1, 1, = 을 입력하면 계산기에는 차례로 x, x+2, x^2+2x, x^3+2x^2, x^3+2x^2+11 이 입력되는 것이다.

문제를 단순하게 하기 위해서 최고차항의 계수는 항상 1이라고 가정하자. 또 음수 계수는 고려하지 않기로 하자.

다항식이 주어졌을 때, 이 계산기로 주어진 다항식을 계산하려면 계산기를 최소 몇 번 눌러야 하는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 다항식의 차수 N(1≤N≤10,000)이 주어진다. 다음 줄에는 다항식의 계수가 최고차항부터 주어진다. 최고차항의 계수는 항상 1이며 모든 계수는 0 이상이다. 모든 계수는 1,000,000,000을 넘지 않는다.

출력

첫째 줄에 계산기를 누르는 최소 횟수를 출력한다.

예제 입력 1

3
1 0 1 11

예제 출력 1

11
W3sicHJvYmxlbV9pZCI6IjIyMDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjYzRcdWMwYjBcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjJlNFx1ZDU2ZFx1YzJkZFx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YWNlMFx1YzU0OFx1YjQxYyBcdWFjYzRcdWMwYjBcdWFlMzBcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhY2M0XHVjMGIwXHVhZTMwXHVjNWQwXHViMjk0IDBcdWJkODBcdWQxMzAgOVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWM2NDAgKywgJnRpbWVzOyhcdWFjZjFcdWQ1NThcdWFlMzApLCB4LCA9XHVjNzU4IDE0XHVhYzFjXHVjNzU4IFx1ZDBhNFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWM3NzQgXHVhY2M0XHVjMGIwXHVhZTMwXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyB4XjMgKyB4ICsgMTFcdWM3NDQgXHVhY2M0XHVjMGIwXHVkNTU4XHViODI0XHViYTc0IHgsICZ0aW1lczssIHgsICZ0aW1lczssIHgsICssIHggKyAxLCAxLCA9IFx1Yzc0NCBcdWIyMDRcdWI5NzRcdWJhNzQgXHViNDFjXHViMmU0LiBcdWI2MTAgeF4zICsgMnheMiArIDExXHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgeCwgKywgMiwgJnRpbWVzOywgeCwgJnRpbWVzOywgeCwgKywgMSwgMSwgPSBcdWM3NDQgXHViMjA0XHViOTc0XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG48cD5cdWM3N2NcdWJjMThcdWM4MDFcdWM3NzggXHVhY2M0XHVjMGIwXHVhZTMwXHViNzdjXHViYTc0IHgsICssIDIsICZ0aW1lczssIHgsICZ0aW1lczssIHgsICssIDEsIDEsID0gXHVjNzQ0IHggKyAyeF4yICsgMTFcdWI4NWMgXHVjNzc4XHVjMmRkXHVkNTU4XHVhY2EwXHVjOWMwXHViOWNjLCBcdWM3NzQgXHVhY2M0XHVjMGIwXHVhZTMwXHViMjk0IFx1Y2Q5NFx1YWMwMCBcdWJhNTRcdWJhYThcdWI5YWNcdWFjMDAgXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFjYzRcdWMwYjBcdWM3NDQgXHVkNTYwIFx1YjU0Y1x1YzVkMCBcdWFjYzRcdWMwYjAgXHVjOWMxXHVjODA0XHVjNWQwIFx1YWNjNFx1YzBiMFx1YWUzMFx1YzVkMCBcdWM4MDBcdWM3YTVcdWI0MThcdWM1YjQgXHVjNzg4XHViMzU4IFx1YWMxMlx1YzVkMCBcdWFjYzRcdWMwYjBcdWM3NDQgXHVkNTVjXHViMmU0LiBcdWM5ODkgeCwgKywgMiwgJnRpbWVzOywgeCwgJnRpbWVzOywgeCwgKywgMSwgMSwgPSBcdWM3NDQgXHVjNzg1XHViODI1XHVkNTU4XHViYTc0IFx1YWNjNFx1YzBiMFx1YWUzMFx1YzVkMFx1YjI5NCBcdWNjMjhcdWI4NDBcdWI4NWMgeCwgeCsyLCB4XjIrMngsIHheMysyeF4yLCB4XjMrMnheMisxMSBcdWM3NzQgXHVjNzg1XHViODI1XHViNDE4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG48cD5cdWJiMzhcdWM4MWNcdWI5N2MgXHViMmU4XHVjMjFjXHVkNTU4XHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjZDVjXHVhY2UwXHVjYzI4XHVkNTZkXHVjNzU4IFx1YWNjNFx1YzIxOFx1YjI5NCBcdWQ1NmRcdWMwYzEgMVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NThcdWM3OTAuIFx1YjYxMCBcdWM3NGNcdWMyMTggXHVhY2M0XHVjMjE4XHViMjk0IFx1YWNlMFx1YjgyNFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFlMzBcdWI4NWMgXHVkNTU4XHVjNzkwLjxcL3A+XHJcbjxwPlx1YjJlNFx1ZDU2ZFx1YzJkZFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVhY2M0XHVjMGIwXHVhZTMwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWIyZTRcdWQ1NmRcdWMyZGRcdWM3NDQgXHVhY2M0XHVjMGIwXHVkNTU4XHViODI0XHViYTc0IFx1YWNjNFx1YzBiMFx1YWUzMFx1Yjk3YyBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YmM4OCBcdWIyMGNcdWI3ZWNcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+IiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjJlNFx1ZDU2ZFx1YzJkZFx1Yzc1OCBcdWNjMjhcdWMyMTggTigxJmxlO04mbGU7MTAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMmU0XHVkNTZkXHVjMmRkXHVjNzU4IFx1YWNjNFx1YzIxOFx1YWMwMCBcdWNkNWNcdWFjZTBcdWNjMjhcdWQ1NmRcdWJkODBcdWQxMzAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNkNWNcdWFjZTBcdWNjMjhcdWQ1NmRcdWM3NTggXHVhY2M0XHVjMjE4XHViMjk0IFx1ZDU2ZFx1YzBjMSAxXHVjNzc0XHViYTcwIFx1YmFhOFx1YjRlMCBcdWFjYzRcdWMyMThcdWIyOTQgMCBcdWM3NzRcdWMwYzFcdWM3NzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWFjYzRcdWMyMThcdWIyOTQgMSwwMDAsMDAwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+Iiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjYzRcdWMwYjBcdWFlMzBcdWI5N2MgXHViMjA0XHViOTc0XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjIwMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBvbGx5IE5vbWlhbHMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBBdmlhbiBDb21wdXRhdGlvbiBNaXNzaW9uIG9mIHRoZSBJbnRlcm5hdGlvbmFsIE9ybml0aG9sb2dpc3RzIFVuaW9uIGlzIGRlZGljYXRlZCB0byB0aGUgc3R1ZHkgb2YgaW50ZWxsaWdlbmNlIGluIGJpcmRzLCBhbmQgc3BlY2kmbWFjcjtjYWxseSB0aGUgc3R1ZHkgb2YgY29tcHV0YXRpb25hbCBhYmlsaXR5LiBPbmUgb2YgdGhlIG1vc3QgcHJvbWlzaW5nIHByb2plY3RzIHNvIGZhciBpcyB0aGUgJnF1b3Q7UG9sbHkgTm9taWFsJnF1b3Q7IHByb2plY3Qgb24gcGFycm90IGludGVsbGlnZW5jZSwgcnVuIGJ5IERyLiBBbGJlcnQgQi4gVHJvc3MgYW5kIGhpcyBhc3Npc3RhbnRzLCBDbGlmZm9yZCBTd2FsbG93IGFuZCBQZXJyeSBLZWV0LiBJbiB0aGUgQUNNLCBwYXJyb3RzIGFyZSB0cmFpbmVkIHRvIGNhcnJ5IG91dCBzaW1wbGUgcG9seW5vbWlhbCBjb21wdXRhdGlvbnMgaW52b2x2aW5nIGludGVnZXJzLCB2YXJpYWJsZXMsIGFuZCBzaW1wbGUgYXJpdGhtZXRpYyBvcGVyYXRvcnMuPFwvcD5cclxuXHJcbjxwPldoZW4gc2hvd24gYSBmb3JtdWxhIGNvbnNpc3Rpbmcgb2YgYSBwb2x5bm9taWFsIHdpdGggbm9uLW5lZ2F0aXZlIGludGVnZXIgY29lJnBsdXNtbjtjaWVudHMgYW5kIG9uZSB2YXJpYWJsZSB4LCBlYWNoIHBhcnJvdCB1c2VzIGEgc3BlY2lhbCBiZWFrLW9wZXJhdGVkIFBEQSwgb3IgJnF1b3Q7UGFycm90IERpZ2l0YWwgQXNzaXN0YW50LCZxdW90OyB0byB0YXAgb3V0IGEgc2VxdWVuY2Ugb2Ygb3BlcmF0aW9ucyBmb3IgY29tcHV0aW5nIHRoZSBwb2x5bm9taWFsLiBUaGUgUERBIG9wZXJhdGVzIG11Y2ggbGlrZSBhIGNhbGN1bGF0b3IuIEl0IGhhcyBrZXlzIG1hcmtlZCB3aXRoIHRoZSBmb2xsb3dpbmcgc3ltYm9sczogdGhlIGRpZ2l0cyBmcm9tIDAgdGhyb3VnaCA5LCB0aGUgc3ltYm9sIGB4JiMzOTssIGFuZCB0aGUgb3BlcmF0b3JzIGArJiMzOTssIGAmdGltZXM7JiMzOTssIGFuZCBgPSYjMzk7LiAoVGhlIHgga2V5IGlzIGludGVybmFsbHkgYXNzb2NpYXRlZCB3aXRoIGFuIGludGVnZXIgY29uc3RhbnQgYnkgQWwgQi4gVHJvc3MgZm9yIHRlc3RpbmcgcHVycG9zZXMsIGJ1dCB0aGUgcGFycm90IHNlZXMgb25seSB0aGUgYHgmIzM5Oy4pIEZvciBpbnN0YW5jZSwgaWYgdGhlIHBhcnJvdCB3ZXJlIHByZXNlbnRlZCB3aXRoIHRoZSBwb2x5bm9taWFsPFwvcD5cclxuXHJcbjxwPng8c3VwPjM8XC9zdXA+ICsgeCArIDExPFwvcD5cclxuXHJcbjxwPnRoZSBwYXJyb3QgbWlnaHQgdGFwIHRoZSBmb2xsb3dpbmcgc2VxdWVuY2Ugb2Ygc3ltYm9sczo8XC9wPlxyXG5cclxuPHA+eCwgJnRpbWVzOywgeCwgJnRpbWVzOywgeCwgKywgeCwgKywgMSwgMSwgPTxcL3A+XHJcblxyXG48cD5UaGUgUERBIGhhcyBubyBleHRyYSBtZW1vcnksIHNvIGVhY2ggJnRpbWVzOyBvciArIG9wZXJhdGlvbiBpcyBhcHBsaWVkIHRvIHRoZSBwcmV2aW91cyBjb250ZW50cyBvZiB0aGUgZGlzcGxheSBhbmQgd2hhdGV2ZXIgc3VjY2VlZGluZyBvcGVyYW5kIGlzIGVudGVyZWQuIElmIHRoZSBwb2x5bm9taWFsIGhhZCBiZWVuPFwvcD5cclxuXHJcbjxwPng8c3VwPjM8XC9zdXA+ICsgMng8c3VwPjI8XC9zdXA+ICsgMTE8XC9wPlxyXG5cclxuPHA+dGhlbiB0aGUgcGFycm90IHdvdWxkIG5vdCBoYXZlIGJlZW4gYWJsZSB0byAmcXVvdDtzYXZlJnF1b3Q7IHRoZSB2YWx1ZSBvZiB4PHN1cD4zPFwvc3VwPiB3aGlsZSBjYWxjdWxhdGluZyB0aGUgdmFsdWUgb2YgMng8c3VwPjI8XC9zdXA+LiBJbnN0ZWFkLCBhIGRpZmZlcmVudCBvcmRlciBvZiBvcGVyYXRpb25zIHdvdWxkIGJlIG5lZWRlZCwgZm9yIGluc3RhbmNlOjxcL3A+XHJcblxyXG48cD54LCArLCAyLCAmdGltZXM7LCB4LCAmdGltZXM7LCB4LCArLCAxLCAxLCA9PFwvcD5cclxuXHJcbjxwPlRoZSBjb3N0IG9mIGEgY2FsY3VsYXRpb24gaXMgdGhlIG51bWJlciBvZiBrZXkgcHJlc3Nlcy4gVGhlIGNvc3Qgb2YgY29tcHV0aW5nIHg8c3VwPjM8XC9zdXA+ICsgeCArIDExIGluIHRoZSBleGFtcGxlIGFib3ZlIGlzIDExIChmb3VyIHByZXNzZXMgb2YgdGhlIHgga2V5LCB0d28gcHJlc3NlcyBvZiBgJnRpbWVzOyYjMzk7LCB0d28gcHJlc3NlcyBvZiBgKyYjMzk7LCB0d28gcHJlc3NlcyBvZiB0aGUgZGlnaXQgYDEmIzM5OywgYW5kIHRoZSBgPSYjMzk7IGtleSkuIEl0IHNvIGhhcHBlbnMgdGhhdCB0aGlzIGlzIHRoZSBtaW5pbWFsIGNvc3QgZm9yIHRoaXMgcGFydGljdWxhciBleHByZXNzaW9uIHVzaW5nIHRoZSBQREEuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgZmluZHMgdGhlIGxlYXN0IGNvc3RseSB3YXkgZm9yIGEgcGFycm90IHRvIGNvbXB1dGUgYSBudW1iZXIgb2YgcG9seW5vbWlhbCBleHByZXNzaW9ucy4gQmVjYXVzZSBwYXJyb3RzIGFyZSwgYWZ0ZXIgYWxsLCBqdXN0IGJpcmQtYnJhaW5zLCB0aGV5IGFyZSBpbnRpbWlkYXRlZCBieSBwb2x5bm9taWFscyB3aG9zZSBoaWdoLW9yZGVyIGNvZWZmaWNpZW50IGlzIGFueSB2YWx1ZSBleGNlcHQgMSwgc28gdGhpcyBjb25kaXRpb24gaXMgYWx3YXlzIGltcG9zZWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCBjb25zaXN0cyBvZiBhIHNlcXVlbmNlIG9mIGxpbmVzLCBlYWNoIGNvbnRhaW5pbmcgYSBwb2x5bm9taWFsIGFuZCBhbiB4IHZhbHVlLiBFYWNoIHBvbHlub21pYWwgYTxzdWI+bjxcL3N1Yj54PHN1cD5uPFwvc3VwPiArIGE8c3ViPm4tMTxcL3N1Yj54PHN1cD5uLTE8XC9zdXA+ICsgLi4uICsgYTxzdWI+MDxcL3N1Yj4gaXMgcmVwcmVzZW50ZWQgYnkgaXRzIGRlZ3JlZSBmb2xsb3dlZCBieSB0aGUgbm9uLW5lZ2F0aXZlIGNvZWZmaWNpZW50cyBhPHN1Yj5uPFwvc3ViPiwgLi4uLCBhPHN1Yj4wPFwvc3ViPiBvZiBkZWNyZWFzaW5nIHBvd2VycyBvZiB4LCB3aGVyZSBhbiBpcyBhbHdheXMgMS4gRGVncmVlcyBhcmUgYmV0d2VlbiAxIGFuZCAxMDAuIFRoZSBjb2VmZmljaWVudHMgYXJlIGZvbGxvd2VkIG9uIHRoZSBzYW1lIGxpbmUgYnkgYW4gaW50ZWdlciB2YWx1ZSBmb3IgdGhlIHZhcmlhYmxlIHgsIHdoaWNoIGlzIGFsd2F5cyBlaXRoZXIgMSBvciAtMS4gVGhlIGlucHV0IGlzIHRlcm1pbmF0ZWQgYnkgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSB2YWx1ZXMgMCAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHBvbHlub21pYWwsIHByaW50IHRoZSBwb2x5bm9taWFsIG51bWJlciBmb2xsb3dlZCBieSB0aGUgdmFsdWUgb2YgdGhlIHBvbHlub21pYWwgYXQgdGhlIGdpdmVuIGludGVnZXIgdmFsdWUgeCBhbmQgdGhlIG1pbmltdW0gY29zdCBvZiBjb21wdXRpbmcgdGhlIHBvbHlub21pYWw7IGltaXRhdGUgdGhlIGZvcm1hdHRpbmcgaW4gdGhlIHNhbXBsZSBvdXRwdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d