두더지굴 timer 1s memory 1024MB

지하에 N개의 방이 있는 두더지굴이 있다. 각 방은 1번부터 N번까지 서로 다른 번호가 붙어 있고, 서로 다른 두 개의 방을 잇는 굴이 N-1개 존재한다. 또한, 임의의 한 방에서 다른 방으로 하나 이상의 굴을 통하여 이동할 수 있음이 보장된다.

처음에 i번 방에 A_i 마리의 두더지가 살고 있다. 모든 방의 두더지의 마리 수는 총 (N), (N+1), (N+2) 중 하나의 값이라는 것이 보장된다.

한 방에 너무 많은 두더지가 몰려있으면 지반이 무너질 수 있기에 모든 방의 두더지 수는 최소 한 마리에서 최대 두 마리까지만 위치해 있어야 한다. 두더지들은 굴을 따라 다른 방으로 자유롭게 이동이 가능한데, 각 두더지가 이동한 거리는 거쳐간 굴의 개수로 정의된다.

지반을 안정화하기 위한 최소 이동 거리의 총합을 구하는 프로그램을 작성하시오.