개폐교 자동 조작

델프트에는 사람이 직접 조작하는 개폐교가 아직 남아 있다. 이 다리를 오래 맡아 온 직원이 곧 은퇴하기 때문에, 시는 다리를 자동으로 올리고 내리는 프로그램을 도입하려 한다.

프로그램은 다음 두 조건을 우선순위 순서대로 지켜야 한다.

1. 어떤 배도 30분보다 오래 기다리게 하지 않는다.
2. 조건 1을 지키면서, 다리를 차량이 통행할 수 없는 시간의 총합을 최소로 만든다.

다리를 올리는 데 60초, 내리는 데 60초가 걸린다. 다리가 움직이는 동안에는 차량도 배도 다리를 지나갈 수 없다. 첫 배가 도착하기 전에 다리는 완전히 내려가 있고, 마지막 배가 지나간 뒤에도 다시 완전히 내려가야 한다.

다리가 완전히 올라간 상태에서 배 한 대가 지나가는 데 20초가 걸린다. 배는 도착한 순서대로 한 대씩 지나간다. 도착한 순간에 다리가 완전히 올라가 있지 않거나 앞의 배가 아직 지나가는 중이면 그 배는 기다린다. 배의 대기 시간은 도착한 순간부터 지나가기 시작하는 순간까지의 길이이고, 이 값이 1800초를 넘으면 안 된다.

지나가는 배가 없는 동안에도 다리를 올린 채로 둘 수 있다. 다음 배가 곧 도착한다면 다리를 내렸다가 다시 올리는 것보다 이렇게 두는 편이 짧게 끝난다.

다리는 올라가기 시작한 순간부터 다시 완전히 내려온 순간까지 차량이 통행할 수 없다. 모든 배의 도착 시각이 주어질 때, 차량이 통행할 수 없는 시간의 총합이 최소가 되도록 다리를 조작하고 그 총합을 구하라.

첫째 줄에 다리를 지나가야 하는 배의 수 $N$이 주어진다 ($1 \le N \le 4000$).

다음 $N$개 줄에는 배 $i$가 다리에 도착하는 시각 $T_i$가 초 단위 정수로 주어진다 ($60 \le T_i \le 100000$).

배는 도착 시각이 증가하는 순서로 주어지고, 두 배의 도착 시각은 20초 이상 떨어져 있다. 즉 $i < j$이면 $T_i + 20 \le T_j$이다.

모든 배가 다리를 지나가게 하는 동안 차량이 다리를 통행할 수 없는 시간의 총합의 최솟값을 초 단위 정수로 한 줄에 출력한다.