You are given a string that contains only the six bracket characters (, ), [, ], {, and }.
The string is balanced when every opening bracket has a matching closing bracket of the same type, the pairs are properly nested, and no closing bracket appears without a matching open bracket before it. An empty string is considered balanced.
Print whether the given string is balanced.
Input format
Line 1: an integer n, the length of the string.
Line 2: the string of exactly n bracket characters. When n is 0 this line is present but empty.
Output format
Print YES if the string is balanced, otherwise print NO.
Constraints
- 0 ≤ n ≤ 100000
- Every character of the string is one of
(,),[,],{,}.