당신은 섬의 해안을 따라 기후를 조사하는 연구팀의 일원이다. 섬의 해안은 둘레가 K킬로미터인 원으로 모델링된다. 해안에는 등대가 하나 있으며, 이는 원 둘레 위의 한 점을 차지한다. 해안 위의 각 점은 [0, K) 범위의 실수 하나에 대응된다. 정확히 말해, x는 등대에서 해안을 따라 시계 방향으로 x킬로미터 걸어간 지점이다. 예를 들어 K = 5라면, 점 0은 등대가 있는 지점, 점 1.5는 등대에서 시계 방향으로 1.5km 떨어진 지점, 점 2.5는 등대와 지름의 반대편에 있는 지점이다.

당신은 해안의 온도를 연구하는 일을 맡았다. 다른 팀은 다음과 같이 동작하는 해안 온도 측정 시스템을 설치했다. 여러 온도계를 특정 지점들에 설치해 그 지점의 온도를 측정한다. 어떤 두 온도계도 같은 지점에 놓이지 않았다. 그 팀의 모델에서는 온도계가 없는 지점의 온도는 가장 가까운 온도계가 측정한 온도와 같다고 가정한다. 두 온도계까지의 거리가 같은 지점에서는, 시계 방향에 있는 온도계(그 지점에서 시계 방향으로 걸었을 때 처음 만나는 온도계)를 사용한다.

불행히도 당신은 온도계가 몇 개였는지, 어디에 놓였는지 알지 못한다. 하지만 시스템의 온도 데이터에는 접근할 수 있다. 데이터는 N개의 값으로 이루어진 두 목록 X₁, X₂, ..., X_N 그리고 T₁, T₂, ..., T_N 으로 주어진다. 이는 다음을 의미한다: 1 ≤ i < N인 각 i에 대해 X_i ≤ x < X_i+1인 모든 점 x에는 온도 T_i가 할당되고, 0 ≤ x < X₁ 또는 X_N ≤ x < K인 모든 점 x에는 온도 T_N가 할당된다. 점들은 시계 방향으로 열거되어 있으므로, 모든 i에 대해 X_i < X_i+1이다.

관측된 데이터를 만들어낼 수 있는 온도계의 최소 개수를 구하고 싶다.

#10378 upload 1 done 1 how_to_reg 1

Thermometers timer 30s memory 1024MB

#10378

Thermometers 30s 1024MB