Valid Event Sequence

You are given a sequence of events where each event is either start or end. Your task is to determine if the sequence is valid.

A sequence is considered valid if and only if every start event is matched with a corresponding end event in the correct order. In other words, as you scan the sequence from left to right, the number of start events minus the number of end events (denoted by \(count\)) should never become negative, and must be zero at the end. Mathematically, if we denote the running count by \(count\), then for every prefix of the sequence we require: \[ count \ge 0 \] and at the end, \[ count = 0 \]

Read the sequence from the input, verify its validity, and output True if it is valid and False otherwise.

inputFormat

The input is given via standard input (stdin) as follows:

• The first line contains a single integer \(n\) (\(0 \le n \le 10^5\)) representing the number of events.
• The second line contains \(n\) space-separated tokens. Each token is either start or end.

outputFormat

Output to standard output (stdout) a single line: True if the event sequence is valid, otherwise False.

## sample

4
start start end end

True

</p>