Шоколадный должок Так вышло, что Антон должен Саше n шоколадок. Он уже закупил нужное число плиток и решил отдавать их Саше по одной в день; осталось лишь определиться с порядком.
Антон знает, что Саше одинаково нравятся шоколадки всех видов, но с одним исключением: девушка совершенно не радуется шоколадке, если она того же вида, что и накануне. Например, получив 10 горьких Милок подряд, Саша порадуется всего один раз, а вот если они будут чередоваться с карамельными, радости будет в 10 раз больше.
Антону вычислить максимально возможную радость Саши.
Входные данные
В первой строке находится число n (1 ≤ n ≤ 10 5 ) — количество шоколадок. В следующей строке находится n чисел a i (1 ≤ a i ≤ 10 6 ) — виды шоколадок, закупленных Антоном.
Выходные данные
Выведите единственное число — максимально возможную радость Саши.
Примеры
входные данные
5
1 2 3 4 5
выходные данные
5
входные данные
5
3 3 4 3 3
выходные данные
3
входные данные
5
3 3 3 3 3
выходные данные
1
const
n = 2;
k = 2;
var
i,j,s:integer;
a:array[1..n,1..k] of integer;
begin
s:=0;
for i:=1 to n do
for j:=1 to k do
begin
Writeln('Введите a[',i,',',j,']:');
readln(a[i,j]);
if a[i,j] mod 2=0 then s:=s+a[i,j];
end;
if s<0 then
for i:=1 to n do
for j:=1 to k do
if j mod 2=0 then
a[i,j]:=1;
if s>=0 then
for i:=1 to n do
for j:=1 to k do
if j mod 2=0 then
a[i,j]:=-1;
for i:=1 to n do
begin
for j:=1 to k do
write('a[':4,i,',',j,']=',a[i,j]);
writeln;
end;
end.
n = 3;
k = 3;
var
i,j,s1,s2:integer;
a:array[1..n,1..k] of integer;
begin
s1:=0;
s2:=0;
for i:=1 to n do
for j:=1 to k do
begin
Writeln('Введите a[',i,',',j,']:');
readln(a[i,j]);
if (a[i,j]>0) and (i<>j) then s1:=s1+a[i,j];
if (a[i,j]<0) and (i<>j) then s2:=s2+a[i,j];
end;
if s1>s2 then
for j:=1 to k do
begin
a[1,j]:=s1;
a[n,j]:=s1;
end;
if s2>=s1 then
for i:=1 to n do
begin
a[i,1]:=s2;
a[i,k]:=s2;
end;
writeln('Полученный массив:');
for i:=1 to n do
begin
for j:=1 to k do
write('a[':4,i,',',j,']=',a[i,j]);
writeln;
end;
end.