A monitoring dashboard logs a stream of labeled tag events. Each event is one token: either an opening tag <name> or a closing tag </name>, where name is 1-10 lowercase English letters. Tags must nest correctly, like in XML/HTML: the most recently opened tag must be the next one closed.
Scan the tokens left to right (1-indexed) and find the first token that breaks correct nesting. A token breaks nesting if it is a closing tag </name> and either no tag is currently open, or the most recently opened (and not yet closed) tag has a different name.
If every closing tag matches correctly but some opened tag is never closed by the end of the stream, the stream is still invalid — in that case report the position of the earliest still-open tag (the first tag ever opened that never got closed).
If neither situation occurs, the stream is fully valid.
Input format
Line 1: an integer n, the number of tokens.
Line 2: n space-separated tokens, each of the form <name> or </name>.
Output format
Print VALID if the whole stream is correctly nested. Otherwise print a single integer: the 1-indexed position described above.
Constraints
- 1 ≤ n ≤ 100000
- Each
nameconsists of 1 to 10 lowercase English letters.