oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

bracket Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

bracket.html

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

Syntax

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110201s256MBMinimum
230421s256MBMinimum
320621s256MBMinimum
440821s256MBMinimum
5021s256MBMinimum

Judge Compile Command

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

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.