Problem Description
Given a bracket sequence of length L, you are to determine if it is valid!
A valid bracket sequence is defined recursively as:
- "" or
- (x) where x is a valid bracket sequence, or
- xy, where x and y are valid bracket sequences.
Limits
For all tests: each character will be a '(' or a ')'.
Subtask 1 (10%): 1 ≤ L ≤ 4.
Subtask 2 (30%): 1 ≤ L ≤ 10.
Subtask 3 (20%): 1 ≤ L ≤ 200.
Subtask 4 (40%): 1 ≤ L ≤ 100 000.
Subtask 5 (0%): Sample Testcases.
Input
The first line of input will contain one integer, L.
The second line of input will contain one string, the bracket sequence.
Output
The output should contain one string, either "Valid" or "Invalid".
Sample Testcase 1
Input
6
(()())
Output
Valid
Sample Testcase 2
Input
8
(())((()
Output
Invalid