프로그램

바이트랜드(Bajtocja)의 방첩 기관은 어떤 적대국이 메시지를 암호화하는 데 쓰는 프로그램을 오랫동안 가로채려 했습니다. 마침내 그 프로그램의 일부, 즉 프로그램에 등장하는 모든 괄호의 나열을 손에 넣었습니다.

프로그램에는 세 종류의 괄호가 나옵니다.

• 소괄호: ( 와 )
• 대괄호: [ 와 ]
• 중괄호: { 와 }

정보량은 적지만, 요원들은 여기서 가능한 한 많은 것을 알아내려 합니다. 이 나열에서 가장 중요한 특성은 괄호 중첩 깊이입니다. 괄호 나열의 중첩 깊이란 각 괄호 쌍이 바로 앞 쌍의 안쪽에 들어 있는 괄호 쌍들의 가장 긴 연쇄의 길이, 다시 말해 서로 중첩된 괄호 쌍의 최대 개수를 뜻합니다.

이 비용이 큰 계산은 가로챈 괄호 문자열이 올바를 때에만 의미가 있습니다. 올바르다는 것은, 각 종류의 여는 괄호를 그보다 뒤에 나오는 같은 종류의 닫는 괄호와 짝지을 수 있고, 그 사이에 있는 괄호들 또한 올바른 괄호 문자열을 이루는 경우를 말합니다.

첫째 줄에 정수 $n$ ($1 \le n \le 1\,000\,000$) 하나가 주어집니다. 이는 프로그램의 길이입니다.

둘째 줄에 (, ), [, ], {, } 문자로 이루어진 문자열이 주어집니다. 이는 프로그램에 차례로 등장하는 괄호들입니다.

입력으로 주어진 괄호 문자열이 올바르면, 괄호의 최대 중첩 깊이를 나타내는 정수 하나를 출력합니다.

올바르지 않으면 NIE 라는 단어 하나만 출력합니다.