#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 10 | 20 | 1s | 256MB | Minimum |

2 | 30 | 42 | 1s | 256MB | Minimum |

3 | 20 | 62 | 1s | 256MB | Minimum |

4 | 40 | 82 | 1s | 256MB | Minimum |

5 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o bracket -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512