제재소

바이트람 마을의 모든 농장은 아주 긴 도로의 한쪽에만 있습니다. 도로 반대편이 바이트랜드 국립공원이기 때문입니다. 시장은 마을 경제를 키우려고 마을 전체가 가구 사업에 뛰어들기로 했습니다.

마을에는 농장과 같은 수의 제재소가 있고, 모두 이 하나뿐인 도로를 따라 늘어서 있습니다. 각 제재소는 정확히 한 농장에만 목재를 공급하고, 각 농장은 정확히 한 제재소에서만 목재를 받습니다. 즉 제재소와 농장은 일대일로 짝지어집니다.

목재는 제재소 하나와 농장 하나를 잇는 짧은 진입로를 따라 운반됩니다. 남쪽은 국립공원이라 아무것도 지을 수 없으므로 모든 진입로는 큰길의 북쪽에 놓이고, 어떤 두 진입로도 서로 교차해서는 안 됩니다.

도로를 따라 있는 지점에 서쪽부터 동쪽으로 $1, 2, \dots, 2n$ 번호를 붙입니다. 위치 $p$ 와 $q$ 를 잇는 진입로의 길이는 $|p - q|$ 입니다. 교차하지 않는 모든 올바른 배정 중에서 진입로 전체 길이의 합이 가장 작은 값을 구하세요.

첫째 줄에 농장의 수 $n$ ($1 \le n \le 1{,}000{,}000$) 이 주어집니다.

둘째 줄에 g 와 t 로만 이루어진 길이 $2n$ 의 문자열이 주어지며, 서쪽부터 동쪽 순서로 각 지점을 나타냅니다. g 는 농장(폴란드어로 gospodarstwo), t 는 제재소(폴란드어로 tartak)를 뜻합니다. 바이트랜드 국립공원은 도로의 남쪽에 있습니다.

올바른 배정이란 모든 농장을 서로 다른 제재소 하나와 연결하며, 모든 진입로가 북쪽에 놓이고 서로 교차하지 않는 것을 말합니다.

올바른 배정이 존재하지 않으면 NIE(폴란드어로 아니오) 한 단어만 한 줄에 출력합니다.

배정이 존재하면, 교차하지 않는 모든 올바른 배정에 대한 진입로 전체 길이의 최솟값을 정수 하나로 출력합니다. 위치 $p$ 와 $q$ 를 잇는 진입로의 길이는 $|p - q|$ 입니다.

제재소(흰 원)와 농장(검은 원)의 배치 예시입니다.

참고: 그림에서 농장, 제재소, 큰길 사이에 간격을 둔 것은 상황을 더 잘 보여 주기 위한 것일 뿐입니다. 실제로는 제재소와 농장이 큰길 바로 옆에 붙어 있어서, 제재소나 농장과 큰길 사이에는 진입로를 놓을 수 없습니다.