시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB67018215237.811%

문제

다항식을 계산하기 위해 고안된 계산기가 있다. 이 계산기에는 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
W3sicHJvYmxlbV9pZCI6IjIyMDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjYzRcdWMwYjBcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjJlNFx1ZDU2ZFx1YzJkZFx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YWNlMFx1YzU0OFx1YjQxYyBcdWFjYzRcdWMwYjBcdWFlMzBcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhY2M0XHVjMGIwXHVhZTMwXHVjNWQwXHViMjk0IDBcdWJkODBcdWQxMzAgOVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWM2NDAgKywgJnRpbWVzOyhcdWFjZjFcdWQ1NThcdWFlMzApLCB4LCA9XHVjNzU4IDE0XHVhYzFjXHVjNzU4IFx1ZDBhNFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVjNzc0IFx1YWNjNFx1YzBiMFx1YWUzMFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgeF4zICsgeCArIDExXHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjgyNFx1YmE3NCB4LCAmdGltZXM7LCB4LCAmdGltZXM7LCB4LCArLCB4ICsgMSwgMSwgPSBcdWM3NDQgXHViMjA0XHViOTc0XHViYTc0IFx1YjQxY1x1YjJlNC4gXHViNjEwIHheMyArIDJ4XjIgKyAxMVx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjXHViMjk0IHgsICssIDIsICZ0aW1lczssIHgsICZ0aW1lczssIHgsICssIDEsIDEsID0gXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3Y1x1YmMxOFx1YzgwMVx1Yzc3OCBcdWFjYzRcdWMwYjBcdWFlMzBcdWI3N2NcdWJhNzQgeCwgKywgMiwgJnRpbWVzOywgeCwgJnRpbWVzOywgeCwgKywgMSwgMSwgPSBcdWM3NDQgeCArIDJ4XjIgKyAxMVx1Yjg1YyBcdWM3NzhcdWMyZGRcdWQ1NThcdWFjYTBcdWM5YzBcdWI5Y2MsIFx1Yzc3NCBcdWFjYzRcdWMwYjBcdWFlMzBcdWIyOTQgXHVjZDk0XHVhYzAwIFx1YmE1NFx1YmFhOFx1YjlhY1x1YWMwMCBcdWM1YzZcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YWNjNFx1YzBiMFx1Yzc0NCBcdWQ1NjAgXHViNTRjXHVjNWQwIFx1YWNjNFx1YzBiMCBcdWM5YzFcdWM4MDRcdWM1ZDAgXHVhY2M0XHVjMGIwXHVhZTMwXHVjNWQwIFx1YzgwMFx1YzdhNVx1YjQxOFx1YzViNCBcdWM3ODhcdWIzNTggXHVhYzEyXHVjNWQwIFx1YWNjNFx1YzBiMFx1Yzc0NCBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSB4LCArLCAyLCAmdGltZXM7LCB4LCAmdGltZXM7LCB4LCArLCAxLCAxLCA9IFx1Yzc0NCBcdWM3ODVcdWI4MjVcdWQ1NThcdWJhNzQgXHVhY2M0XHVjMGIwXHVhZTMwXHVjNWQwXHViMjk0IFx1Y2MyOFx1Yjg0MFx1Yjg1YyB4LCB4KzIsIHheMisyeCwgeF4zKzJ4XjIsIHheMysyeF4yKzExIFx1Yzc3NCBcdWM3ODVcdWI4MjVcdWI0MThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWI5N2MgXHViMmU4XHVjMjFjXHVkNTU4XHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjZDVjXHVhY2UwXHVjYzI4XHVkNTZkXHVjNzU4IFx1YWNjNFx1YzIxOFx1YjI5NCBcdWQ1NmRcdWMwYzEgMVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NThcdWM3OTAuIFx1YjYxMCBcdWM3NGNcdWMyMTggXHVhY2M0XHVjMjE4XHViMjk0IFx1YWNlMFx1YjgyNFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFlMzBcdWI4NWMgXHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWQ1NmRcdWMyZGRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YWNjNFx1YzBiMFx1YWUzMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViMmU0XHVkNTZkXHVjMmRkXHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjgyNFx1YmE3NCBcdWFjYzRcdWMwYjBcdWFlMzBcdWI5N2MgXHVjZDVjXHVjMThjIFx1YmE4NyBcdWJjODggXHViMjBjXHViN2VjXHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmU0XHVkNTZkXHVjMmRkXHVjNzU4IFx1Y2MyOFx1YzIxOCBOKDEgJmxlOyBOICZsZTsgMTAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMmU0XHVkNTZkXHVjMmRkXHVjNzU4IFx1YWNjNFx1YzIxOFx1YWMwMCBcdWNkNWNcdWFjZTBcdWNjMjhcdWQ1NmRcdWJkODBcdWQxMzAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNkNWNcdWFjZTBcdWNjMjhcdWQ1NmRcdWM3NTggXHVhY2M0XHVjMjE4XHViMjk0IFx1ZDU2ZFx1YzBjMSAxXHVjNzc0XHViYTcwIFx1YmFhOFx1YjRlMCBcdWFjYzRcdWMyMThcdWIyOTQgMCBcdWM3NzRcdWMwYzFcdWM3NzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWFjYzRcdWMyMThcdWIyOTQgMSwwMDAsMDAwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhY2M0XHVjMGIwXHVhZTMwXHViOTdjIFx1YjIwNFx1Yjk3NFx1YjI5NCBcdWNkNWNcdWMxOGMgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMjAwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUG9sbHkgTm9taWFscyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIEF2aWFuIENvbXB1dGF0aW9uIE1pc3Npb24gb2YgdGhlIEludGVybmF0aW9uYWwgT3JuaXRob2xvZ2lzdHMgVW5pb24gaXMgZGVkaWNhdGVkIHRvIHRoZSBzdHVkeSBvZiBpbnRlbGxpZ2VuY2UgaW4gYmlyZHMsIGFuZCBzcGVjaSZtYWNyO2NhbGx5IHRoZSBzdHVkeSBvZiBjb21wdXRhdGlvbmFsIGFiaWxpdHkuIE9uZSBvZiB0aGUgbW9zdCBwcm9taXNpbmcgcHJvamVjdHMgc28gZmFyIGlzIHRoZSAmcXVvdDtQb2xseSBOb21pYWwmcXVvdDsgcHJvamVjdCBvbiBwYXJyb3QgaW50ZWxsaWdlbmNlLCBydW4gYnkgRHIuIEFsYmVydCBCLiBUcm9zcyBhbmQgaGlzIGFzc2lzdGFudHMsIENsaWZmb3JkIFN3YWxsb3cgYW5kIFBlcnJ5IEtlZXQuIEluIHRoZSBBQ00sIHBhcnJvdHMgYXJlIHRyYWluZWQgdG8gY2Fycnkgb3V0IHNpbXBsZSBwb2x5bm9taWFsIGNvbXB1dGF0aW9ucyBpbnZvbHZpbmcgaW50ZWdlcnMsIHZhcmlhYmxlcywgYW5kIHNpbXBsZSBhcml0aG1ldGljIG9wZXJhdG9ycy48XC9wPlxyXG5cclxuPHA+V2hlbiBzaG93biBhIGZvcm11bGEgY29uc2lzdGluZyBvZiBhIHBvbHlub21pYWwgd2l0aCBub24tbmVnYXRpdmUgaW50ZWdlciBjb2UmcGx1c21uO2NpZW50cyBhbmQgb25lIHZhcmlhYmxlIHgsIGVhY2ggcGFycm90IHVzZXMgYSBzcGVjaWFsIGJlYWstb3BlcmF0ZWQgUERBLCBvciAmcXVvdDtQYXJyb3QgRGlnaXRhbCBBc3Npc3RhbnQsJnF1b3Q7IHRvIHRhcCBvdXQgYSBzZXF1ZW5jZSBvZiBvcGVyYXRpb25zIGZvciBjb21wdXRpbmcgdGhlIHBvbHlub21pYWwuIFRoZSBQREEgb3BlcmF0ZXMgbXVjaCBsaWtlIGEgY2FsY3VsYXRvci4gSXQgaGFzIGtleXMgbWFya2VkIHdpdGggdGhlIGZvbGxvd2luZyBzeW1ib2xzOiB0aGUgZGlnaXRzIGZyb20gMCB0aHJvdWdoIDksIHRoZSBzeW1ib2wgYHgmIzM5OywgYW5kIHRoZSBvcGVyYXRvcnMgYCsmIzM5OywgYCZ0aW1lczsmIzM5OywgYW5kIGA9JiMzOTsuIChUaGUgeCBrZXkgaXMgaW50ZXJuYWxseSBhc3NvY2lhdGVkIHdpdGggYW4gaW50ZWdlciBjb25zdGFudCBieSBBbCBCLiBUcm9zcyBmb3IgdGVzdGluZyBwdXJwb3NlcywgYnV0IHRoZSBwYXJyb3Qgc2VlcyBvbmx5IHRoZSBgeCYjMzk7LikgRm9yIGluc3RhbmNlLCBpZiB0aGUgcGFycm90IHdlcmUgcHJlc2VudGVkIHdpdGggdGhlIHBvbHlub21pYWw8XC9wPlxyXG5cclxuPHA+eDxzdXA+MzxcL3N1cD4gKyB4ICsgMTE8XC9wPlxyXG5cclxuPHA+dGhlIHBhcnJvdCBtaWdodCB0YXAgdGhlIGZvbGxvd2luZyBzZXF1ZW5jZSBvZiBzeW1ib2xzOjxcL3A+XHJcblxyXG48cD54LCAmdGltZXM7LCB4LCAmdGltZXM7LCB4LCArLCB4LCArLCAxLCAxLCA9PFwvcD5cclxuXHJcbjxwPlRoZSBQREEgaGFzIG5vIGV4dHJhIG1lbW9yeSwgc28gZWFjaCAmdGltZXM7IG9yICsgb3BlcmF0aW9uIGlzIGFwcGxpZWQgdG8gdGhlIHByZXZpb3VzIGNvbnRlbnRzIG9mIHRoZSBkaXNwbGF5IGFuZCB3aGF0ZXZlciBzdWNjZWVkaW5nIG9wZXJhbmQgaXMgZW50ZXJlZC4gSWYgdGhlIHBvbHlub21pYWwgaGFkIGJlZW48XC9wPlxyXG5cclxuPHA+eDxzdXA+MzxcL3N1cD4gKyAyeDxzdXA+MjxcL3N1cD4gKyAxMTxcL3A+XHJcblxyXG48cD50aGVuIHRoZSBwYXJyb3Qgd291bGQgbm90IGhhdmUgYmVlbiBhYmxlIHRvICZxdW90O3NhdmUmcXVvdDsgdGhlIHZhbHVlIG9mIHg8c3VwPjM8XC9zdXA+IHdoaWxlIGNhbGN1bGF0aW5nIHRoZSB2YWx1ZSBvZiAyeDxzdXA+MjxcL3N1cD4uIEluc3RlYWQsIGEgZGlmZmVyZW50IG9yZGVyIG9mIG9wZXJhdGlvbnMgd291bGQgYmUgbmVlZGVkLCBmb3IgaW5zdGFuY2U6PFwvcD5cclxuXHJcbjxwPngsICssIDIsICZ0aW1lczssIHgsICZ0aW1lczssIHgsICssIDEsIDEsID08XC9wPlxyXG5cclxuPHA+VGhlIGNvc3Qgb2YgYSBjYWxjdWxhdGlvbiBpcyB0aGUgbnVtYmVyIG9mIGtleSBwcmVzc2VzLiBUaGUgY29zdCBvZiBjb21wdXRpbmcgeDxzdXA+MzxcL3N1cD4gKyB4ICsgMTEgaW4gdGhlIGV4YW1wbGUgYWJvdmUgaXMgMTEgKGZvdXIgcHJlc3NlcyBvZiB0aGUgeCBrZXksIHR3byBwcmVzc2VzIG9mIGAmdGltZXM7JiMzOTssIHR3byBwcmVzc2VzIG9mIGArJiMzOTssIHR3byBwcmVzc2VzIG9mIHRoZSBkaWdpdCBgMSYjMzk7LCBhbmQgdGhlIGA9JiMzOTsga2V5KS4gSXQgc28gaGFwcGVucyB0aGF0IHRoaXMgaXMgdGhlIG1pbmltYWwgY29zdCBmb3IgdGhpcyBwYXJ0aWN1bGFyIGV4cHJlc3Npb24gdXNpbmcgdGhlIFBEQS48XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBmaW5kcyB0aGUgbGVhc3QgY29zdGx5IHdheSBmb3IgYSBwYXJyb3QgdG8gY29tcHV0ZSBhIG51bWJlciBvZiBwb2x5bm9taWFsIGV4cHJlc3Npb25zLiBCZWNhdXNlIHBhcnJvdHMgYXJlLCBhZnRlciBhbGwsIGp1c3QgYmlyZC1icmFpbnMsIHRoZXkgYXJlIGludGltaWRhdGVkIGJ5IHBvbHlub21pYWxzIHdob3NlIGhpZ2gtb3JkZXIgY29lZmZpY2llbnQgaXMgYW55IHZhbHVlIGV4Y2VwdCAxLCBzbyB0aGlzIGNvbmRpdGlvbiBpcyBhbHdheXMgaW1wb3NlZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IGNvbnNpc3RzIG9mIGEgc2VxdWVuY2Ugb2YgbGluZXMsIGVhY2ggY29udGFpbmluZyBhIHBvbHlub21pYWwgYW5kIGFuIHggdmFsdWUuIEVhY2ggcG9seW5vbWlhbCBhPHN1Yj5uPFwvc3ViPng8c3VwPm48XC9zdXA+ICsgYTxzdWI+bi0xPFwvc3ViPng8c3VwPm4tMTxcL3N1cD4gKyAuLi4gKyBhPHN1Yj4wPFwvc3ViPiBpcyByZXByZXNlbnRlZCBieSBpdHMgZGVncmVlIGZvbGxvd2VkIGJ5IHRoZSBub24tbmVnYXRpdmUgY29lZmZpY2llbnRzIGE8c3ViPm48XC9zdWI+LCAuLi4sIGE8c3ViPjA8XC9zdWI+IG9mIGRlY3JlYXNpbmcgcG93ZXJzIG9mIHgsIHdoZXJlIGFuIGlzIGFsd2F5cyAxLiBEZWdyZWVzIGFyZSBiZXR3ZWVuIDEgYW5kIDEwMC4gVGhlIGNvZWZmaWNpZW50cyBhcmUgZm9sbG93ZWQgb24gdGhlIHNhbWUgbGluZSBieSBhbiBpbnRlZ2VyIHZhbHVlIGZvciB0aGUgdmFyaWFibGUgeCwgd2hpY2ggaXMgYWx3YXlzIGVpdGhlciAxIG9yIC0xLiBUaGUgaW5wdXQgaXMgdGVybWluYXRlZCBieSBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIHZhbHVlcyAwIDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggcG9seW5vbWlhbCwgcHJpbnQgdGhlIHBvbHlub21pYWwgbnVtYmVyIGZvbGxvd2VkIGJ5IHRoZSB2YWx1ZSBvZiB0aGUgcG9seW5vbWlhbCBhdCB0aGUgZ2l2ZW4gaW50ZWdlciB2YWx1ZSB4IGFuZCB0aGUgbWluaW11bSBjb3N0IG9mIGNvbXB1dGluZyB0aGUgcG9seW5vbWlhbDsgaW1pdGF0ZSB0aGUgZm9ybWF0dGluZyBpbiB0aGUgc2FtcGxlIG91dHB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d