카드컨트롤 (Hard)

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

1. 준석이가 제일 위에 있는 카드를 가져간다.
2. 수현이가 다음 카드를 가져간다.
3. 준석이의 카드와 수현이의 카드가 같으면 무승부, 다른 카드면 O가 적힌 카드를 가진 사람의 점수가 1점 추가된다.

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

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

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

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

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

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