Совсем скоро произойдёт запуск самого нового, мощного и необычного коллайдера, который расположен вдоль прямой. В нём будут запущены n частиц. Все они расположены на одной прямой, причем в одной точке не может быть двух или более частиц. Координаты частиц совпадают с расстоянием в метрах от центра коллайдера, то есть xi — это и координата i-й частицы, и одновременно её позиция в коллайдере. Все координаты частиц — целые чётные числа.
Про каждую частицу известно направление её движения — она будет двигаться либо влево, либо вправо после старта коллайдера. Все частицы начнут двигаться одновременно в момент старта коллайдера. Каждая частица будет двигаться ровно влево или ровно вправо с постоянной скоростью 1 метр в микросекунду. Считайте, что коллайдер достаточно большой, и частицы не могут вылететь из него за обозримое время.
Напишите программу, которая найдет момент первого столкновения двух каких-либо частиц коллайдера. Иными словами, требуется найти количество микросекунд до первого такого момента, когда какие-либо две частицы окажутся в одной точке.
Выходные данные
В первой строке выведите единственное целое число — первый момент времени (в микросекундах), в который две частицы окажутся в одной точке и произойдет взрыв.
Выведите единственное целое число -1, если столкновения частиц не произойдет.
Примечание
В первом примере из условия первый взрыв произойдёт через 1 микросекунду, так как частицы с номерами 1 и 2 одновременно окажутся в точке с координатой 3.
Во втором примере из условия взрыв никогда не произойдёт, так как никакие две частицы никогда не окажутся в одной точке одновременно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
RLRL
2 4 6 10
|
1
|
|
2
|
3
LLR
40 50 60
|
-1
|