문제
선아는 최근에 어떤 미생물을 연구하고 있다. 선아는 연구 과정에서 이 미생물 여러 마리를 한 줄로 나열하면 미생물이 한 마리만 남을 때까지 다음 규칙들에 따라 미생물들이 서로 흡수한다는 사실을 알아냈다.
- 하루에 한 번 줄의 맨 앞에 있는 미생물부터 각 미생물은 차례대로 인접한 미생물 중 자신보다 크기가 작거나 같은 것들을 전부 흡수한다. 다른 미생물을 흡수한 경우, 미생물의 크기는 흡수한 미생물의 크기의 합만큼 커진다.
- 흡수당한 미생물은 사라지며 행동할 수 없다. 즉, 3ドル,ドル 2ドル,ドル 1ドル$의 크기를 가지는 세 마리의 미생물들이 있는 경우 2ドル$는 자신의 차례가 오기 전에 3ドル$에게 흡수당하기 때문에 하루가 지난 후 남아있는 미생물들의 크기는 5ドル,ドル 1ドル$이 된다.
- 흡수하는 미생물은 하루에 흡수할 모든 미생물을 한 번에 흡수한다. 즉, 3ドル,ドル 4ドル,ドル 5ドル$의 크기를 가지는 세 마리의 미생물들이 있고 4ドル$의 차례인 경우 4ドル$는 3ドル$만 흡수한다. 4ドル$가 3ドル$을 흡수해서 7ドル$이 된 후 같은 날 5ドル$를 흡수하는 행동은 불가능하다. 따라서 하루가 지난 후 남아있는 미생물들의 크기는 7ドル,ドル 5ドル$가 된다.
선아에게는 이 미생물이 $N$마리 있다. 이 $N$마리의 미생물들이 한 줄로 나열되었을 때 마지막에 남는 미생물의 최종 크기와 초기 위치를 찾는 프로그램을 작성해 보자.
출력
첫 번째 줄에 마지막에 남는 미생물의 최종 크기를 출력한다.
두 번째 줄에 그 미생물의 초기 위치를 출력한다.
W3sicHJvYmxlbV9pZCI6IjMwODg1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHUwM2E2XHUwMGIyIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMjBcdWM1NDRcdWIyOTQgXHVjZDVjXHVhZGZjXHVjNWQwIFx1YzViNFx1YjVhNCBcdWJiZjhcdWMwZGRcdWJiM2NcdWM3NDQgXHVjNWYwXHVhZDZjXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjMTIwXHVjNTQ0XHViMjk0IFx1YzVmMFx1YWQ2YyBcdWFjZmNcdWM4MTVcdWM1ZDBcdWMxMWMgXHVjNzc0IFx1YmJmOFx1YzBkZFx1YmIzYyBcdWM1ZWNcdWI3ZWMgXHViOWM4XHViOWFjXHViOTdjIFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHViMDk4XHVjNWY0XHVkNTU4XHViYTc0IFx1YmJmOFx1YzBkZFx1YmIzY1x1Yzc3NCA8c3Ryb25nPlx1ZDU1YyBcdWI5YzhcdWI5YWNcdWI5Y2MgXHViMGE4XHVjNzQ0IFx1YjU0Y1x1YWU0Y1x1YzljMDxcL3N0cm9uZz4gXHViMmU0XHVjNzRjIFx1YWRkY1x1Y2U1OVx1YjRlNFx1YzVkMCBcdWI1MzBcdWI3N2MgXHViYmY4XHVjMGRkXHViYjNjXHViNGU0XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWQ3NjFcdWMyMThcdWQ1NWNcdWIyZTRcdWIyOTQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YzU0Y1x1YzU0NFx1YjBjOFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT48c3Ryb25nPlx1ZDU1OFx1YjhlOFx1YzVkMCBcdWQ1NWMgXHViYzg4PFwvc3Ryb25nPiBcdWM5MDRcdWM3NTggXHViOWU4IFx1YzU1ZVx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYmY4XHVjMGRkXHViYjNjXHViZDgwXHVkMTMwIFx1YWMwMSBcdWJiZjhcdWMwZGRcdWJiM2NcdWM3NDAgPHN0cm9uZz5cdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWM8XC9zdHJvbmc+IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWJiZjhcdWMwZGRcdWJiM2MgXHVjOTExIFx1Yzc5MFx1YzJlMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFlMzBcdWFjMDAgPHN0cm9uZz5cdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwPFwvc3Ryb25nPiBcdWFjODNcdWI0ZTRcdWM3NDQgXHVjODA0XHViZDgwIFx1ZDc2MVx1YzIxOFx1ZDU1Y1x1YjJlNC4gXHViMmU0XHViOTc4IFx1YmJmOFx1YzBkZFx1YmIzY1x1Yzc0NCBcdWQ3NjFcdWMyMThcdWQ1NWMgXHVhY2JkXHVjNmIwLCBcdWJiZjhcdWMwZGRcdWJiM2NcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IFx1ZDc2MVx1YzIxOFx1ZDU1YyBcdWJiZjhcdWMwZGRcdWJiM2NcdWM3NTggXHVkMDZjXHVhZTMwXHVjNzU4IFx1ZDU2OVx1YjljY1x1ZDA3YyBcdWNlZTRcdWM5YzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1ZDc2MVx1YzIxOFx1YjJmOVx1ZDU1YyBcdWJiZjhcdWMwZGRcdWJiM2NcdWM3NDAgXHVjMGFjXHViNzdjXHVjOWMwXHViYTcwIFx1ZDU4OVx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWM5ODksICQzJCwgJDIkLCAkMSRcdWM3NTggXHVkMDZjXHVhZTMwXHViOTdjIFx1YWMwMFx1YzljMFx1YjI5NCBcdWMxMzggXHViOWM4XHViOWFjXHVjNzU4IFx1YmJmOFx1YzBkZFx1YmIzY1x1YjRlNFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwICQyJFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjYzI4XHViODQwXHVhYzAwIFx1YzYyNFx1YWUzMCBcdWM4MDRcdWM1ZDAgJDMkXHVjNWQwXHVhYzhjIFx1ZDc2MVx1YzIxOFx1YjJmOVx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVkNTU4XHViOGU4XHVhYzAwIFx1YzljMFx1YjA5YyBcdWQ2YzQgXHViMGE4XHVjNTQ0XHVjNzg4XHViMjk0IFx1YmJmOFx1YzBkZFx1YmIzY1x1YjRlNFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgJDUkLCAkMSRcdWM3NzQgXHViNDFjXHViMmU0LiA8XC9saT5cclxuXHQ8bGk+XHVkNzYxXHVjMjE4XHVkNTU4XHViMjk0IFx1YmJmOFx1YzBkZFx1YmIzY1x1Yzc0MCBcdWQ1NThcdWI4ZThcdWM1ZDAgXHVkNzYxXHVjMjE4XHVkNTYwIFx1YmFhOFx1YjRlMCBcdWJiZjhcdWMwZGRcdWJiM2NcdWM3NDQgXHVkNTVjIFx1YmM4OFx1YzVkMCBcdWQ3NjFcdWMyMThcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgJDMkLCAkNCQsICQ1JFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWI5N2MgXHVhYzAwXHVjOWMwXHViMjk0IFx1YzEzOCBcdWI5YzhcdWI5YWNcdWM3NTggXHViYmY4XHVjMGRkXHViYjNjXHViNGU0XHVjNzc0IFx1Yzc4OFx1YWNlMCAkNCRcdWM3NTggXHVjYzI4XHViODQwXHVjNzc4IFx1YWNiZFx1YzZiMCAkNCRcdWIyOTQgJDMkXHViOWNjIFx1ZDc2MVx1YzIxOFx1ZDU1Y1x1YjJlNC4gJDQkXHVhYzAwICQzJFx1Yzc0NCBcdWQ3NjFcdWMyMThcdWQ1NzRcdWMxMWMgJDckXHVjNzc0IFx1YjQxYyBcdWQ2YzQgXHVhYzE5XHVjNzQwIFx1YjBhMCAkNSRcdWI5N2MgXHVkNzYxXHVjMjE4XHVkNTU4XHViMjk0IFx1ZDU4OVx1YjNkOVx1Yzc0MCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWQ1NThcdWI4ZThcdWFjMDAgXHVjOWMwXHViMDljIFx1ZDZjNCBcdWIwYThcdWM1NDRcdWM3ODhcdWIyOTQgXHViYmY4XHVjMGRkXHViYjNjXHViNGU0XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCAkNyQsICQ1JFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjMTIwXHVjNTQ0XHVjNWQwXHVhYzhjXHViMjk0IFx1Yzc3NCBcdWJiZjhcdWMwZGRcdWJiM2NcdWM3NzQgJE4kXHViOWM4XHViOWFjIFx1Yzc4OFx1YjJlNC4gXHVjNzc0ICROJFx1YjljOFx1YjlhY1x1Yzc1OCBcdWJiZjhcdWMwZGRcdWJiM2NcdWI0ZTRcdWM3NzQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWIwOThcdWM1ZjRcdWI0MThcdWM1YzhcdWM3NDQgXHViNTRjIFx1YjljOFx1YzljMFx1YjljOVx1YzVkMCBcdWIwYThcdWIyOTQgXHViYmY4XHVjMGRkXHViYjNjXHVjNzU4IFx1Y2Q1Y1x1Yzg4NSBcdWQwNmNcdWFlMzBcdWM2NDAgXHVjZDA4XHVhZTMwIFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU3NCBcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiZjhcdWMwZGRcdWJiM2NcdWI0ZTRcdWM3NTggXHVjMjE4ICROJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMVxcbGUgTlxcbGUgNTAwXFwsIDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmJmOFx1YzBkZFx1YmIzY1x1YjRlNFx1Yzc1OCBcdWNkMDhcdWFlMzAgXHVkMDZjXHVhZTMwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCAkTiRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICAkYV8xLGFfMixcXGxkb3RzICxhX04kXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkYV9pJFx1YjI5NCAkaSRcdWJjODhcdWM5ZjggXHViYmY4XHVjMGRkXHViYjNjXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWQwNmNcdWFlMzBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWFjMDEgXHViYmY4XHVjMGRkXHViYjNjXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWQwNmNcdWFlMzBcdWIyOTQgJDEkIFx1Yzc3NFx1YzBjMSAkTiQgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1YWMxOVx1Yzc0MCBcdWNkMDhcdWFlMzAgXHVkMDZjXHVhZTMwXHViOTdjIFx1YWMwMFx1YzljMFx1YjI5NCBcdWI0NTAgXHViYmY4XHVjMGRkXHViYjNjXHVjNzQwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjljOFx1YzljMFx1YjljOVx1YzVkMCBcdWIwYThcdWIyOTQgXHViYmY4XHVjMGRkXHViYjNjXHVjNzU4IFx1Y2Q1Y1x1Yzg4NSBcdWQwNmNcdWFlMzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFkZjggXHViYmY4XHVjMGRkXHViYjNjXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMwODg1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiXHUwM2E2XHUwMGIyIiwiZGVzY3JpcHRpb24iOiI8cD5TZW9uYWggaGFzIHJlY2VudGx5IHN0YXJ0ZWQgcmVzZWFyY2hpbmcgY2VydGFpbiBtaWNyb29yZ2FuaXNtcy4gRHVyaW5nIGhlciByZXNlYXJjaCwgc2hlIGRpc2NvdmVyZWQgdGhhdCBpZiB5b3UgbGluZSB1cCBzZXZlcmFsIG9mIHRoZXNlIG1pY3Jvb3JnYW5pc21zLCB0aGV5IGFic29yYiBlYWNoIG90aGVyIDxzdHJvbmc+dW50aWwgdGhlcmUgaXMgb25seSBvbmUgcmVtYWluaW5nPFwvc3Ryb25nPiwgYWNjb3JkaW5nIHRvIHRoZSBmb2xsb3dpbmcgcnVsZXMuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+PHN0cm9uZz5PbmNlIGEgZGF5PFwvc3Ryb25nPiwgc3RhcnRpbmcgZnJvbSB0aGUgbWljcm9vcmdhbmlzbSBhdCB0aGUgZnJvbnQgb2YgdGhlIGxpbmUgPHN0cm9uZz5pbiB0aGUgb3JkZXIgdGhleSBhcmUgc3RhbmRpbmc8XC9zdHJvbmc+LCBlYWNoIG1pY3Jvb3JnYW5pc20gYWJzb3JicyBhbGwgYWRqYWNlbnQgbWljcm9vcmdhbmlzbXMgdGhhdCBhcmUgPHN0cm9uZz5zbWFsbGVyIHRoYW4gb3IgZXF1YWwgaW4gc2l6ZSB0byBpdHNlbGY8XC9zdHJvbmc+LiBUaGUgbWljcm9vcmdhbmlzbSYjMzk7cyBzaXplJm5ic3A7aW5jcmVhc2VzJm5ic3A7YnkgdGhlIHN1bSBvZiB0aGUgc2l6ZXMgb2YgdGhlIG1pY3Jvb3JnYW5pc21zIGFic29yYmVkLjxcL2xpPlxyXG5cdDxsaT5BYnNvcmJlZCBtaWNyb29yZ2FuaXNtcyBkaXNhcHBlYXIgYW5kIGNhbm5vdCBhY3QuIEZvciBleGFtcGxlLCBpbiB0aGUgY2FzZSB3aGVyZSB0aGVyZSBhcmUgdGhyZWUgbWljcm9vcmdhbmlzbXMgd2l0aCBzaXplcyAkMyQsICQyJCwgYW5kICQxJCwgcmVzcGVjdGl2ZWx5LCAkMiQgaXMgYWJzb3JiZWQgYnkgJDMkIGJlZm9yZSBpdHMgdHVybiBhcnJpdmVzIGFuZCBjYW5ub3QgYWN0LiBUaGUgc2l6ZXMgb2YgdGhlIHJlbWFpbmluZyBtaWNyb29yZ2FuaXNtcyBhZnRlciBvbmUgZGF5IGFyZSwgdGhlcmVmb3JlLCAkNSQgYW5kICQxJC48XC9saT5cclxuXHQ8bGk+VGhlIGFic29yYmluZyBtaWNyb29yZ2FuaXNtIGFic29yYnMgYWxsIHRoZSBtaWNyb29yZ2FuaXNtcyBpdCBpcyB0byBhYnNvcmIgaW4gYSBkYXkgYXQgb25jZS4gRm9yIGV4YW1wbGUsIGxldCZyc3F1bztzIGFzc3VtZSB0aGUgY2FzZSB3aGVyZSB0aGVyZSBhcmUgdGhyZWUgbWljcm9vcmdhbmlzbXMgd2l0aCBzaXplcyAkMyQsICQ0JCwgYW5kICQ1JCwgcmVzcGVjdGl2ZWx5LiBXaGVuIGl0IGlzICQ0JCZyc3F1bztzIHR1cm4sICQ0JCBvbmx5IGFic29yYnMgJDMkLiBBZnRlciAkNCQgYWJzb3JicyAkMyQgKHRodXMgYmVjb21pbmcgJDckKSwgaXQgY2Fubm90IGFic29yYiAkNSQgYWZ0ZXJ3YXJkIG9uIHRoZSBzYW1lIGRheS4gVGhlIHNpemVzIG9mIHRoZSByZW1haW5pbmcgbWljcm9vcmdhbmlzbXMgYWZ0ZXIgb25lIGRheSBhcmUsIHRoZXJlZm9yZSwgJDckIGFuZCAkNSQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+U2VvbmFoIGhhcyAkTiQgb2YgdGhpcyBtaWNyb29yZ2FuaXNtLiBHaXZlbiB0aGUgaW5pdGlhbCBzaXplcyBhbmQgcG9zaXRpb25zIG9mIHRoZXNlICROJCBtaWNyb29yZ2FuaXNtcywgd3JpdGUgYSBwcm9ncmFtIHRoYXQgZmluZHMgdGhlIGZpbmFsIHNpemUgYW5kIGluaXRpYWwgcG9zaXRpb24gb2YgdGhlIGxhc3QgbWljcm9vcmdhbmlzbSByZW1haW5pbmcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyICROJC4gJCgxXFxsZSBOXFxsZSA1MDBcXCwgMDAwKSQ8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zICROJCBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJGFfMSxhXzIsXFxsZG90cyAsYV9OJC4gJGFfaSQgZGVub3RlcyB0aGUgaW5pdGlhbCBzaXplIG9mIHRoZSAkaSQtdGggbWljcm9vcmdhbmlzbS4gVGhlIHNpemUgb2YgZWFjaCBtaWNyb29yZ2FuaXNtIGlzIGJldHdlZW4gJDEkIGFuZCAkTiQgaW5jbHVzaXZlLiBObyB0d28gbWljcm9vcmdhbmlzbXMgaGF2ZSB0aGUgc2FtZSBpbml0aWFsIHNpemUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBmaW5hbCBzaXplIG9mIHRoZSBsYXN0IG1pY3Jvb3JnYW5pc20gcmVtYWluaW5nLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIGluaXRpYWwgcG9zaXRpb24gb2YgdGhlIG1pY3Jvb3JnYW5pc20uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==