어떤 건물의 엘리베이터는 항상 1층에서 출발한다. 사용자들은 가고 싶은 목표 층을 순서대로 입력하고, 엘리베이터는 입력된 순서대로 각 목표 층으로 이동한다.

엘리베이터가 현재 있는 층과 다른 층이 요청되면 그 층으로 이동하여 한 번 멈춘다. 하지만 이미 머물러 있는 층과 같은 층이 요청되면 엘리베이터는 움직이지 않으므로 멈춤으로 세지 않는다.

예를 들어 1층에서 시작하여 \(3, 3, 1, 5\) 가 차례로 요청되면, \(1 \to 3\) (멈춤), \(3 \to 3\) (무시), \(3 \to 1\) (멈춤), \(1 \to 5\) (멈춤) 이 되어 총 \(3\) 번 멈춘다.

요청된 목표 층들의 수열이 주어질 때, 엘리베이터가 총 몇 번 멈추는지 구하는 프로그램을 작성하라.

\(0 \le N \le 200{,}000\)

각 목표 층 번호는 \(1 \le f \le 1{,}000{,}000{,}000\) 인 정수이다.

엘리베이터는 항상 \(1\) 층에서 출발한다.

첫째 줄에 요청의 개수 \(N\) (\(0 \le N \le 200{,}000\)) 이 주어진다.

\(N \ge 1\) 이면 둘째 줄에 공백으로 구분된 \(N\) 개의 정수가 순서대로 주어지며, 각각은 요청된 목표 층 번호이다. \(N = 0\) 이면 둘째 줄은 비어 있거나 없을 수 있다.

각 층 번호는 \(1\) 이상 \(1{,}000{,}000{,}000\) 이하의 정수이다.

엘리베이터가 멈추는 총 횟수를 한 줄에 출력한다.

riseoj 작성

출처 Original