Program

Interview

Time limit1sMemory limit512 MB

Summary

Check whether the bracket string is correct and print its maximum nesting depth, or NIE when it is not.

Level: Easy3 of 10
Topics: Stack
Solved: No attempts yet

Problem

Byteland's counterintelligence service has long been trying to intercept a program that a hostile country uses to encrypt its messages. It has finally obtained a part of that program: the sequence of all the brackets that appear in it.

Three kinds of brackets appear in the program:

round: ( and )
square: [ and ]
curly: { and }

Even though this is very little information, the agents want to deduce as much as they can from it. The most important property of such a sequence is its nesting depth. The nesting depth of a bracket sequence is the length of the longest chain of bracket pairs in which each pair lies directly inside the previous one; in other words, the largest number of mutually nested bracket pairs.

This costly computation only makes sense when the intercepted bracket string is correct. A string is correct when every opening bracket of each kind can be matched with a later closing bracket of the same kind, so that the brackets between them also form a correct bracket sequence.

Input

The first line contains a single integer $n$ ( $1 \le n \le 1\,000\,000$ ), the length of the program.

The second line contains a string made up of the characters (, ), [, ], {, }. These are the brackets that appear in the program, in order.

Output

If the bracket string given on input is correct, print a single integer equal to the maximum nesting depth of the brackets.

Otherwise, print the single word NIE.

Examples2

Example 1
Input
```
20
{}([{()()[]}]()[{}])
```
Expected output
```
4
```
Example 2
Input
```
3
{}}
```
Expected output
```
NIE
```