신호 장애

한 지하철 노선은 길이가 m인 두 평행 레일로 이루어져 있다. 위쪽 레일의 열차는 오른쪽에서 왼쪽으로, 아래쪽 레일의 열차는 왼쪽에서 오른쪽으로 움직인다. 열차가 레일의 끝에 도착하면 즉시 반대편 레일로 옮겨 방향을 바꾸고 계속 진행한다. 이 전환에는 시간이 걸리지 않는다.

평상시 열차들은 항상 1분에 1칸의 일정한 속도로 움직이며, 노선 전체에 균등하게 배치되어 있다. 따라서 레일 위의 임의의 한 점을 지나는 열차도 일정한 주기로 나타난다. 역에서 정차하거나 승객을 태우는 시간은 무시한다.

장애가 발생하면 열차들의 위치가 레일 위에 임의로 흩어진다. 관제 센터는 현재 위치가 주어진 모든 열차를 가능한 한 빨리 다시 균등하게 배치하려고 한다. 센터는 열차를 잠시 멈추게 할 수 있고, 언제든지 방향을 반대로 바꿀 수도 있다. 방향을 바꾸면 열차는 같은 위치의 반대편 레일로 옮겨진다.

위 그림은 길이가 100인 레일을 보여준다. 열차들은 5(오른쪽), 35(왼쪽), 46(왼쪽), 75(왼쪽), 85(오른쪽)에 있다. 예를 들어 46에 있는 열차를 한 칸 움직인 뒤 방향을 바꾸면 균등한 배치를 만들 수 있지만, 이것이 가장 빠른 방법은 아니다.

첫째 줄에 레일의 길이 m과 열차의 수 n이 주어진다. 다음 n개 줄에는 각 열차의 현재 위치 xi와 방향이 주어진다. 방향이 L이면 왼쪽, R이면 오른쪽을 향하고 있다는 뜻이다.

모든 열차를 균등하게 배치하는 데 필요한 최소 시간을 출력한다. 절대 또는 상대 오차가 10^{-6} 이하이면 정답으로 인정된다.

• 100 ≤ m ≤ 100,000,000
• 1 ≤ n ≤ 100,000
• 0 ≤ xi ≤ m