Однажды утром Cereal Guy обнаружил, что все его хлопья пропали. Вместо них он нашел записку. Оказывается, его хитроумный сосед спрятал хлопья в одном из n ящиков. Ящики стоят в один ряд, они пронумерованы от 1 до n слева направо. Сосед оставил подсказки вида: «Спрятано левее i-го ящика» ("To the left of i"), «Спрятано правее i-го ящика» ("To the right of i"). Такие подсказки означают, что в i-ом ящике так же нет хлопьев. Cereal Guy хочет узнать минимальное количество ящиков, которые ему нужно обязательно проверить, чтобы найти хлопья с учетом всех подсказок, либо выяснить, что подсказки противоречат и сосед его обманул, то есть ни в одном из ящиков нет хлопьев.
Выходные данные
В ответе должно содержаться ровно одно число — количество ящиков, которые обязательно нужно проверить, или "-1", если подсказки противоречивы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
To the left of 2
|
1
|
|
2
|
3 2
To the right of 1
To the right of 2
|
1
|
|
3
|
3 1
To the left of 3
|
2
|
|
4
|
3 2
To the left of 2
To the right of 1
|
-1
|