Port Robot

Interview

Time limit10sMemory limit1024 MB

Summary

Given a log where lowercase letters store containers and uppercase letters remove them, decide whether each removal takes the top container and storage ends empty.

Level: Easy3 of 10
Topics: Stack, String
Solved: No attempts yet

Problem

You are developing a robot that helps store containers that have arrived at a port before they are sent to ships. The robot handles these containers using limited space. The space can hold multiple containers stacked one on top of another, but not side by side, as shown in the figure.

While operating, the robot performs two actions:

Storing a container.
Taking a container out of storage.

The port uses 26 container types, each identified by a letter of the Latin alphabet. Each time the robot performs an action, it logs the container type in lowercase when storing a container and in uppercase when taking one out. Your task is to check whether the robot's logs indicate stable operation. In stable operation, every container taken out (action 2) must be in storage and must be in the topmost position. Stable operation also always ends with empty storage.

For example, consider the log 'cdDC'. This is stable. The robot stores 'c' and then 'd', so 'd' is on top. It takes out the first 'd', then takes out 'c'. By contrast, the log 'cdCD' is unstable, because the robot cannot take out 'c' before 'd' is removed.

Input

The first line contains the length of the log generated by the robot. The second line contains the log of the robot's operations.

Output

Print 0 if the log indicates wrong operation, and 1 if the operation is stable.

Examples2

Example 1
Input
```
8
DdaacCAA
```
Expected output
```
0
```
Example 2
Input
```
14
aabcdDCBdDAbBA
```
Expected output
```
1
```