댄스 패드 최소 에너지

한 플레이어가 네 방향 발판 게임을 한다. 발판에는 가운데와 네 방향 지점이 있으며, 가운데를 0, 위를 1, 왼쪽을 2, 아래를 3, 오른쪽을 4로 번호를 붙인다.

처음에는 두 발이 모두 가운데(0)에 있다. 지시가 하나 주어질 때마다 왼발 또는 오른발 중 하나만 움직여 해당 지점을 눌러야 한다.

게임 시작 직후의 (0, 0) 상태를 제외하면 두 발이 같은 지점에 있을 수 없다. 따라서 한 발이 이미 어떤 지점에 있고 다음 지시도 같은 지점이라면, 그 지점에 있는 발로 다시 눌러야 한다.

발을 움직일 때 드는 힘은 다음과 같다.

• 가운데(0)에서 다른 지점으로 움직이면 2
• 같은 지점을 다시 누르면 1
• 인접한 지점으로 움직이면 3
• 반대편 지점으로 움직이면 4

수열 1 2 2 4는 (0, 0) -> (0, 1) -> (2, 1) -> (2, 1) -> (2, 4)처럼 움직이면 힘이 8 든다. 이보다 적은 힘으로는 모든 지시를 만족할 수 없다.

입력은 지시를 나타내는 정수 수열이다. 각 지시는 1, 2, 3, 4 중 하나이며 각각 위, 왼쪽, 아래, 오른쪽 발판을 뜻한다.

정수 0은 수열의 끝을 뜻하며, 입력의 마지막에 한 번 주어진다. 0을 제외한 지시의 개수는 100,000을 넘지 않는다.

모든 지시를 만족하는 데 필요한 힘의 최솟값을 한 줄에 출력한다.