Problem description

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 a₁, a₂, …, a_N. Dzięki temu łatwo obliczyć, że odległość pomiędzy punktami a_i oraz a_j wynosi |a_i−a_j|. 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 a₁, a₂, …, a_N – pozycje każdego z punktów na prostej. Możesz założyć, że dla każdego możliwego i zachodzi a_i < a_i + 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 ≤ a_i ≤ 10⁹.

Przykłady

2
1 3

2

4
1 2 3 4

7