Müasir incəsənət 3

Picowso-nun rəsmi bir ölçülü rənglər massivindən ibarətdir, burada uzunluğu n olan hər rəng 1..n intervalında tam ədədlə təmsil olunur.

Moonet bu cür rəsmi belə kopyalayır: müəyyən bir intervalı bir rənglə boyayır, boya quruyana qədər gözləyir, sonra başqa bir intervalı boyayır və s. Moonet n rənglərindən hər birini istədiyi qədər (bəlkə də heç birini) istifadə edə bilər.

Picowso-nun rəsmini kopyalamaq üçün Moonet-in minimal fırça hərəkətlərinin sayını hesablayın.

Giriş Məlumatları

Birinci sətir n ədədini (1 ≤ n ≤ 300) ehtiva edir.

Növbəti sətir Picowso-nun rəsminin hər bir hüceyrəsinin rəngini göstərən 1..n intervalında n tam ədəd ehtiva edir.

Çıxış Məlumatları

Rəsmi kopyalamaq üçün minimal fırça hərəkətlərinin sayını çıxarın.

Nümunə

Bu nümunədə, Moonet rəsmi belə kopyalaya bilər: (boyanmamış hüceyrələri 0 rəngi ilə göstəririk).

• Əvvəlcə bütün massiv boyanmamışdır:

0 0 0 0 0 0 0 0 0 0

• Moonet ilk 9 hüceyrəni 1 rəngi ilə boyayır:

1 1 1 1 1 1 1 1 1 0

• Moonet intervalı 2 rəngi ilə boyayır:

1 2 2 2 2 2 2 2 1 0

• Moonet intervalı 3 rəngi ilə boyayır:

1 2 3 3 3 3 3 2 1 0

• Moonet intervalı 4 rəngi ilə boyayır:

1 2 3 4 4 4 3 2 1 0

• Moonet bir hüceyrəni 1 rəngi ilə boyayır:

1 2 3 4 1 4 3 2 1 0

• Moonet son hüceyrəni 6 rəngi ilə boyayır:

1 2 3 4 1 4 3 2 1 6

Qeyd edək ki, birinci fırça hərəkətində 1 rəngi ilə onuncu hüceyrəni də boyamaq olardı. Bu, son vəziyyəti dəyişməzdi.