스트림 지연

라이브 스트림 시청자는 종종 원치 않는 스트림 지연을 겪는다. 지연은 네트워크 속도 저하, 높은 스트림 해상도, 클라이언트 하드웨어의 처리 능력 부족 등 여러 이유로 발생할 수 있다. 이 문제에서는 가상의 스트림 하나를 모델링하여 스트림 지연을 계산한다.

스트림의 영상 콘텐츠는 전송할 n개의 네트워크 패킷으로 나뉘어 있으며, 패킷에는 1부터 n까지 번호가 붙어 있다. 각 패킷은 스트리밍되는 영상의 일부를 담고 있고, 길이는 정확히 1초다. 스트림 지연이란 스트림 패킷이 도착하기를 기다리는 동안 시청자가 아무 콘텐츠도 보지 못하는 시간 구간이다. 지연을 전혀 겪지 않는 이상적인 시청자는 i번째 초가 시작될 때 패킷 i를 받으며, 이 경우 스트리밍되는 영상 전체를 끊김 없이 시청할 수 있다.

실제로는 n개의 패킷 중 어느 것이든 아무 시점에 도착할 수 있고, 반드시 1부터 n까지 순서대로 도착하지도 않는다. 스트림 클라이언트는 앞선 패킷을 모두 재생한 경우에만 패킷 i를 재생하기 시작한다. 그렇지 않으면 i보다 앞선 패킷을 모두 받아 재생할 때까지 기다린다. 스트림 클라이언트는 아직 재생할 수 없는 수신 패킷을 버퍼에 보관하며, 재생할 준비가 되면 즉시 꺼내 쓸 수 있다. 재생할 시점에 패킷이 없으면 스트림이 지연되고 시청자는 라이브 스트림보다 뒤처진다. 스트림 클라이언트는 각 패킷을 원래 속도로 정확히 1초 동안 재생한다. 재생 시점이 라이브 스트림보다 훨씬 뒤처지더라도 모든 패킷을 재생해야 한다.

n개 패킷의 도착 시각이 시간순으로 주어질 때, 스트림 시청자가 겪는 총 지연 시간을 계산하라.

첫째 줄에 정수 n (1 ≤ n ≤ 1,000)이 주어진다. 이어서 n개의 줄이 주어진다. i번째 줄에는 두 정수 ti와 i (1 ≤ ti ≤ 109, 1 ≤ i ≤ n)가 주어지며, 이는 패킷 i가 ti번째 초가 시작될 때 도착한다는 뜻이다. ti 값은 감소하지 않는다. 패킷 여러 개가 같은 시각에 도착할 수 있다.

주어진 패킷 도착 시각을 바탕으로 총 지연 시간을 출력한다.