카드컨트롤 (Hard)

면접 대비

시간 제한1초메모리 제한512 MB

요약

O 카드 N장과 X 카드 N장이 섞인 문자열이 주어질 때, 카드 한 장을 맨 위로 올리는 조작을 최소 몇 번 해야 준석이가 이기는지 구합니다.

문제

준석이와 수현이는 카드게임을 하고 있다. O가 적힌 카드 $N$ 장, X가 적힌 카드 $N$ 장이 섞여 있다. 게임은 다음 순서로 진행된다.

마지막에 점수가 높은 사람이 이긴다.

준석이는 게임 시작 전에 카드를 조작할 수 있다. 정확히는 한 번의 조작으로 원하는 카드 하나를 빼내서 카드의 제일 위에 올리는 동작을 할 수 있다.

준석이가 초기 배치를 안다고 할 때, 최소한의 조작으로 준석이가 이기려면 몇 번 조작해야 하는가?

첫 번째 줄에 $N$ 이 주어진다. ( $1 \leq N \leq 10^6$ )

다음 줄에 위에 있는 카드부터 순서대로 카드에 적혀있는 문양이 주어진다.

카드의 최소 조작 횟수를 출력한다.