Джерримендеринг — разделение территории на избирательные округа неестественным образом с целью искусственного изменения соотношения политических сил в них и, как следствие, в целом на территории проведения выборов. Например, при необходимости обеспечить победу на территории партии $$$X$$$ (если от одного избирательного округа избирается один кандидат или один выборщик), нужно всех противников $$$X$$$ сосредоточить по округам, где $$$X$$$ не сможет выиграть, а всех сторонников $$$X$$$ распределить так, чтобы они обеспечивали уверенную победу с небольшим перевесом в нужных округах. Например, в тесте из условия всего за $$$X$$$ голосует 10 человек, а против $$$X$$$ голосует 15 человек, но, благодаря специальному разделению по округам, $$$X$$$ выигрывает в двух избирательных округах из трёх.
В этой задаче избирательная территория представляет собой улицу, на которой в ряд расположены $$$N$$$ домов. В $$$i$$$-м доме проживает $$$a_i$$$ человек, и все они голосуют одинаково: либо за партию $$$X$$$, либо за другую партию. Улицу необходимо разбить на три избирательных округа, от каждого избирательного округа будет избираться один кандидат, и необходимо произвести такую нарезку улицы на три избирательных округа, чтобы минимум в двух округах из трёх выиграл кандидат от партии $$$X$$$. Кандидат от партии $$$X$$$ выигрывает, если за него голосует более половины избирателей, проживающих в домах данного избирательного округа. Но чтобы вас не заподозрили в джерримендеринге, необходимо, чтобы каждый избирательный округ представлял собой непрерывный отрезок из номеров домов, то есть сначала вдоль по улице идут дома первого избирательного округа, затем — второго, затем — третьего. Каждый избирательный округ должен содержать как минимум один дом.
Первая строка входных данных содержит целое число $$$N$$$ ($$$3\le N\le 10^5$$$) — количество домов на улице. Следующие $$$N$$$ строк содержат по одному целому числу $$$a_i$$$ ($$$0 \lt |a_i|\le 10^4$$$). Если $$$a_i \gt 0$$$, то в $$$i$$$-м доме проживает $$$a_i$$$ избирателей, голосующих за кандидата от партии $$$X$$$. Если $$$a_i \lt 0$$$, то в $$$i$$$-м доме проживает $$$|a_i|$$$ избирателей, голосующих против кандидата от партии $$$X$$$.
Если возможно разделить $$$N$$$ домов на три округа так, что минимум в двух округах выигрывает кандидат от партии $$$X$$$, программа должна вывести три целых положительных числа $$$N_1$$$, $$$N_2$$$, $$$N_3$$$, $$$N_1+N_2+N_3=N$$$, соответствующих количеству домов в первом, втором и третьем избирательном округе от начала улицы. При таком разбиении минимум в двух округах из трёх должен выигрывать кандидат от партии $$$X$$$. Если возможно несколько таких разбиений, необходимо вывести любое из них.
Если искомое разбиение не существует, программа должна вывести одно число 0.
Решения, правильно работающие при $$$N\le 100$$$, будут оцениваться в 40 баллов.
Решения, правильно работающие при $$$N\le 1000$$$, будут оцениваться в 70 баллов.
7 -3 -5 3 -4 2 5 -3
4 1 2
Пояснение к примеру из условия. На улице расположены 7 домов, избиратели в них распределены так: $$$(-3, -5, 3, -4, 2, 5, -3)$$$. Правильный ответ: 4, 1, 2. При таком разбиении в первом округе оказываются 4 дома: $$$(-3, -5, 3, -4)$$$. В этом округе за $$$X$$$ голосует 3 избирателя, против — 12 избирателей и $$$X$$$ разгромно проигрывает. В следующем округе один дом, в котором 2 избирателя голосуют за $$$X$$$, в этом округе $$$X$$$ выиграет. В третьем округе два дома: $$$(5, -3)$$$, и в этом округе $$$X$$$ тоже выиграет. Итого $$$X$$$ выигрывает в двух округах.
| Название |
|---|


