32094번 - スライムの合成 다국어

문제

JAG 王国ではスライムの異常発生が深刻な問題になっている.魔法使いであるあなたは,スライムの数を減らすために「スライム合成魔法」を開発した.

JAG 王国のスライムには非負整数で表される「レベル」がついており,スライム合成魔法ではこのレベルが重要な意味合いを持つ.スライム合成魔法を発動すると,同じレベル X である二匹のスライムを合成して,レベル X+1 のスライム一匹にすることができるのだ.

これによってスライムの数を減らすことができることを確信したあなたはスライム異常発生の現場へと急行した.

現場では,n 匹のスライムが一列に並べられている.はじめ,左から i 番目のスライムのレベルは L_i である.スライム合成魔法は列で隣り合う同じレベルの二匹のスライムにしか発動出来ず,条件を満たすスライムのペアが存在しない場合には発動することも出来ない.スライム合成魔法によって合成されたスライムは,元の二体のスライムの位置の中間に生まれる.スライムが勝手に移動することはなく,移動させることもできない.

たとえば,スライムのレベルの列が (1, 1, 1, 1) の場合,左から 2 番目のスライムと 3 番目のスライムにスライム合成魔法を発動すると,発動後のスライムのレベルの列は (1, 2, 1) になり,これ以上スライム合成魔法を発動することはできない.

スライム合成魔法は発動直前に条件を満たしていれば,どのスライムのペアにも発動することができる.最適な順序でスライム合成魔法を発動した場合,あなたは最大何匹のスライムを減らすことができるか,つまり最大何回スライム合成魔法を発動できるかを求めよ.

入力で与えられるスライムのレベルは 0 から 9 までであるが,スライム合成魔法によってレベル 10 以上のスライムを生成することが可能であることに注意せよ.

입력

入力は複数のデータセットからなる.データセットの個数は 40 を超えない.各データセットは次の形式で表される.

n

L

1 行目には整数 n が与えられ,1 ≤ n ≤ 2 × 10⁵ を満たす.2 行目には数字列 L が与えられ,その長さが n である.この数字列の i 番目の数字 L_i は,左から i 番目のスライムのレベルであり,0 以上 9 以下であることが保証される.

入力の終わりは 1 つのゼロからなる行で表される.

출력

各データセットについて,最適な順序でスライム合成魔法を発動したとき最大何回発動できるかを答えよ.

제한

힌트