Problem description


Akrobatyka
(I)
Limit pamięci: 256 MB
Limit czasu: 1.00 s

Jedna z ulubionych gier Jasia to trzecia część serii Pradawnych Zwojów. Fabuła i wspaniały otwarty świat są zdecydowanie dużymi atutami, jednak Jasio najbardziej ceni w niej niezbalansowane, absurdalne wręcz mechaniki rozgrywki.

Jedno z ciekawszych rozwiązań zastosowanych w grze to poziom postaci w akrobatyce, która pozwala na częstsze i, o zgrozo, wyższe skakanie. Znacząco wyższe! Gra co prawda ogranicza maksymalny poziom umiejętności do 100, ale od czego są w końcu modyfikacje! Jaś świetnie bawi się przeskakując jednym skokiem całe budynki, jednak jak to mówią: “Z wielką mocą przychodzi wielka… chęć większej mocy”, czy jakoś tak. Zdobywanie kolejnych poziomów akrobatyki zaczyna być dość nużącym zajęciem, więc Jaś obmyślił plan na urozmaicenie sobie tego procesu.

Jaś wyznaczył prostą przecinającą całą wyspę i wyznaczył na niej N wartych odwiedzenia miejsc, po czym oznaczył je punktami o współrzędnych a1, a2, …, aN. Dzięki temu łatwo obliczyć, że odległość pomiędzy punktami ai oraz aj wynosi |aiaj|. Oczywiście nie ma on najmniejszej ochoty podróżować Łazikiem (tak, jest to oficjalne tłumaczenie) jak każdy inny gracz przy zdrowych zmysłach. Aby zwiększać poziom akrobacji, Jaś zamierza po prostu… skakać. Jako, że posiada już kilkutysięczny poziom, jego postać jest w stanie przeskoczyć z jednego końca wyspy na drugi!

Pomóż mu wybrać kolejność odwiedzania wybranych lokacji tak, aby w każdej był dokładnie raz, a jednocześnie zmaksymalizował otrzymane doświadczenie w akrobacji, czyli sumarycznie przebył możliwie najdłuższą trasę. Jasio musi rozpocząć i zakończyć swoją trasę w pewnych spośród wybranych miejsc, ale może je wybrać dowolnie.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N, oznaczająca liczbę ciekawych miejsc wyznaczonych przez Jasia. W kolejnym wierszu znajduje się N różnych liczb całkowitych a1, a2, …, aN – pozycje każdego z punktów na prostej. Możesz założyć, że dla każdego możliwego i zachodzi ai < ai + 1.

Wyjście

W jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą, oznaczającą długość najdłuższej trasy, jaką postać Jasia jest w stanie przeskoczyć, odwiedzając każde ciekawe miejsce dokładnie raz.

Ograniczenia

2 ≤ N ≤ 100 000, 1 ≤ ai ≤ 109.

Przykłady

Wejście Wyjście
2
1 3
2
Wejście Wyjście Wyjaśnienie
4
1 2 3 4
7

W tym przypadku Jasiowi opłaca się na przykład zacząć na polu 3, po czym przeskakiwać kolejno na pola o pozycjach 1, 4 i 2.