Бизнесмен Василий готовится к уплате налогов за квартал (три месяца). Действующая налоговая система в государстве, в котором Василий ведет свой бизнес, устроена таким образом, что величина налога зависит от прибыли в конце каждого месяца. Чистая прибыль бизнесмена определяется как разница между доходом и расходом. Разумеется, если бизнес идет не очень удачно, прибыль бизнесмена может быть отрицательной —в этом случае речь идет об убытке. Все доходы и расходы Василий записывал в журнал в виде целых чисел. Теперь Василий должен подать налоговую декларацию с суммой доходов на конец каждого месяца, другими словами ему необходимо поделить последовательность записей в журнале на три непустые части.
При этом Василий хочет сделать это таким образом, чтобы прибыль в каждой части была одинаковой (возможно даже отрицательной) — в этом случае сумма налога будет минимальной. Менять порядок записей в журнале нельзя.
По имеющимся данным определите количество выполнить такое разбиение.
Входные данные
В первой строке входных данных содержится единственное целое число N — количество записей в журнале Василия (3 ≤ N ≤ 105).
В следующих N строках записаны целые числа ai, соответствующие записям в журнале (−108 ≤ ai ≤ 108).
Выходные данные
Программа должна вывести единственное целое число — количество выполнить необходимое разбиение.
n,k,i:integer;
begin
for n:=1 to 2 do
begin
writeln('Введите строку ',n,':');
readln(s);
k:=0;
for i:=1 to length(s) do
begin
case s[i] of
'[': k:=k+1;
']': k:=k-1;
end;
end;
if k=0
then writeln('В строке ',s,' количество [ и ] одинаково')
else writeln('В строке ',s,' количество [ и ] не одинаково');
end;
end.
Пример:
Введите строку 1:
c:=a[imax,j]; a[imax,j]:=a[imin,j]; a[imin,j]:=c
В строке c:=a[imax,j]; a[imax,j]:=a[imin,j]; a[imin,j]:=c количество [ и ] одинаково
Введите строку 2:
Просто [ пример ]] со [[ скобками
В строке Просто [ пример ]] со [[ скобками количество [ и ] не одинаково