25348번 - 등산 게임

문제

돌은 캐릭터를 조작하여 등산을 하며 돌을 수집하는 게임을 하고 있다.

캐릭터한테는 에너지가 있으며, 최대치는 $E$이다. 초기에 캐릭터는 높이 0에 있으며, 에너지를 $E$만큼 가지고 있다.

캐릭터를 조작하는 동작은 두 가지이다. 한 번에 두 개 이상의 동작을 사용하는 것은 불가능하다.

• 캐릭터가 산 꼭대기인 높이 $H$에 있지 않으며 캐릭터의 에너지가 1 이상일 경우, 위 방향키를 눌러 높이 1만큼 산을 오를 수 있다. 이 동작을 할 경우 캐릭터는 에너지를 1 잃는다.
• 캐릭터가 지표면인 높이 0에 있지 않을 경우, 아래 방향키를 눌러 높이 1만큼 산에서 미끄러져 내려올 수 있다. 이 동작은 에너지를 소모하지 않는다.

지표면과 산 꼭대기에는 에너지를 회복할 수 있는 쉼터가 있다. 만약 캐릭터가 쉼터에 있을 경우, 에너지가 자동으로 최대로 채워진다.

이 게임에는 수집 요소인 돌이 $N$개 있는데, 돌은 반드시 순서대로 수집해야 하며, $i$번째로 수집해야 하는 돌의 위치는 $P_i$이다. $i$번째 돌은 $(i-1)$번째까지의 돌을 모두 수집한 이후 $P_i$의 높이에 도달할 경우 자동으로 얻어진다. 특히, 첫 번째 돌은 $P_1$의 높이에 있는 경우 자동으로 얻어진다.

초기 상태에서 산을 올라 돌을 모두 수집하고 다시 높이 0까지 돌아오는 데 걸리는 최소 동작 횟수를 구하자.

입력

첫 번째 줄에 세 자연수 $E,ドル $H,ドル $N$이 주어진다.

두 번째 줄에 $N$개의 자연수가 주어진다. $i$번째로 주어지는 자연수는 $P_i$이다.

출력

초기 상태에서 산을 올라 돌을 모두 수집하고 다시 높이 0까지 돌아오는 데 걸리는 최소 동작 횟수를 출력한다.

제한

• 1ドル \le E \le 10^{15}$
• 0ドル \le H \le 10^9$
• 1ドル \le N \le 200,000円$
• 0ドル \le P_i \le H$ (1ドル \le i \le N$)
• $P_i \ne P_{i+1}$ (1ドル \le i \le N-1$)
• 모든 돌을 수집할 수 있는 경우만 입력으로 주어진다.

힌트