Anomaly Mahjong 1

Interview

Time limit1sMemory limit1024 MB

Summary

Given a sequence of mahjong tiles, find the position of the first tile whose kind appears a fifth time, or print 0 if no kind reaches five.

Level: Easy2 of 10
Topics: Array, Implementation
Solved: No attempts yet

Problem

A tile (牌) in mahjong comes in 34 kinds, with 4 copies of each kind, for 136 tiles in total. The kinds are as follows.

Shape	Name
	Character tiles (萬數牌)
There are 9 kinds, 1m to 9m, labeled by the Chinese character on the tile.
	Circle tiles (筒數牌)
There are 9 kinds, 1p to 9p, labeled by the number of circles drawn on the tile.
	Bamboo tiles (索數牌)
There are 9 kinds, 1s to 9s, labeled by the number of bamboo sticks drawn on the tile.
	Honor tiles (字牌)
There are 7 kinds, 1z to 7z, labeled by the character printed on the tile.

You are placing mahjong tiles one by one, shuffled, to learn their shapes. You have not yet noticed one thing. Some tiles are undergoing an anomaly.

Each kind of tile has 4 copies in mahjong, but an anomalous tile changes its kind, so in some cases 5 or more tiles of the same kind can appear.

While you lay out the tiles, you must notice the anomaly and resolve it when 5 or more tiles of the same kind have appeared. Find the moment when you can notice the anomaly.

Input

The first line contains the number of tiles $N$ to lay out. $(1 \le N \le 136)$

The second line contains the $N$ tiles in the order you place them, separated by spaces. Every tile in the input is one of the 34 kinds described above.

Output

Print $i$ if you can notice the anomaly after placing the $i$ -th tile. If you lay out every tile and still do not notice the anomaly, print 0 instead.

Examples2

Example 1
Input
```
8
1z 2z 5z 5z 5z 5z 5z 3z
```
Expected output
```
7
```

Example 2

Input

13
1m 1m 1m 2m 3m 4m 5m 6m 7m 8m 9m 9m 9m

Expected output