Даша решила совершить путешествие. Перед этим она выбрала $$$N$$$ городов, которые она хотела бы увидеть и для каждого города $$$i$$$ определила его красоту $$$x_{i}$$$.
Посетить город можно двумя способами:
Даша хочет посетить все города последовательно и получить от этого максимальное удовольствие. Подскажите ей, какой максимальное удовольствие от такого путешествия она может получить.
В первой строке ввода дано целое число $$$n$$$ — количество городов, которые миьноны хотят посетить ($$$1 \le n \le 10^6$$$).
Во второй строке ввода перечислены целые числа $$$a_i$$$ — значения перспективности городов в том же порядке, в котором их необходимо посетить ($$$-10^6 \le a_i \le 10^6$$$).
Выведите единственное целое число — максимальное удовольствие, которое можно получить посещая города последовательно, начиная с города под номером $$$1$$$.
6 3 5 1 6 5 0 1
82
6 -1 4 4 1 1 5 9
138