Hide

Problem D
Bracket Matching

Given a bracket sequence $s$ of length $n$, you are to determine if it is valid!

A valid bracket sequence is defined recursively as:

  • “”

  • $(x)$ where $x$ is a valid bracket sequence

  • $[x]$ where $x$ is a valid bracket sequence

  • $\{ x\} $ where $x$ is a valid bracket sequence

  • $xy$, where $x$ and $y$ are valid bracket sequences

Input

The first line of each contains one integer n $(2\leq n\leq 100\, 000)$ — the length of the bracket sequence.

The second line of each test case contains a string $s$ — the bracket sequence in the question. It is guaranteed that $s$ only contains $()[]\{ \} $ as characters.

Output

Output a single integer — the answer to the problem.

Sample Input 1 Sample Output 1
6
([]{})
Valid
Sample Input 2 Sample Output 2
8
(())((()
Invalid
Sample Input 3 Sample Output 3
6
([}{])
Invalid
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Author
Zhang Guangxuan
Source NUS Competitive Programming
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in