You like tracking airplane flights a lot. Specifically, you maintain history of an airplane’s flight at several instants and record them in your notebook. Today, you have recorded N such records h1, h2, ..., hN, denoting the heights of some airplane at several instants. These records mean that airplane was first flying on height h1, then started changing its height to h2, then from h2 to h3 and so on. The airplanes are usually on cruise control while descending or ascending, so 
you can assume that plane will smoothly increase/decrease its height from hi to hi + 1 with a constant speed. You can see that during this period, the airplane will cover all possible heights in the range [min(hi, hi+1), max(hi, hi+1)] (both inclusive). It is easy to see that the plane will be at all possible heights in the range exactly a single instant of time during this ascend/descend.

You are interested in finding the maximum integer K such that the plane was at some height exactly K times during the flight.

-----Input-----
There is a single test case.
First line of the input contains an integer N denoting the number of records of heights of the plane.
Second line contains N space separated integers denoting h1, h2, ..., hN.

-----Output-----
Output a single maximum integer K in one line, such that the plane was at some height exactly K times during the flight.

-----Constraints-----
- hi ≠ hi+1

-----Subtasks-----
Subtask #1: (30 points)
- 1 ≤ N ≤ 1000
- 1 ≤ hi ≤ 1000

Subtask #2: (70 points)
- 1 ≤ N ≤ 105
- 1 ≤ hi ≤ 109

-----Example-----
Input:
5
1 2 3 2 3

Output:
3

-----Explanation-----

The flight can be draw as:

3  /\/
2 /
1

There are infinitely many heights at which the plane was 3 times during the flight, for example 2.5, 2.1. Notice that the plane was only 2 times at height 2. Moreover, there are no height at which the plane was more than 3 times, so the answer is 3.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def f(n):\n\n s = list(map(int, input().split()))\n low = []\n high = []\n\n for i in range(n - 1):\n  low.append(min(s[i], s[i+1]))\n  high.append(max(s[i], s[i+1]))\n low.sort()\n high.sort()\n curr = mx = 0\n i = j = 0\n n -= 1\n while i < n and j < n:\n  if low[i] < high[j]:\n   i += 1\n   curr += 1\n  else:\n   j += 1\n   curr -= 1\n  mx = max(mx, curr)\n\n return mx \n \nn = int(input())\nprint(f(n))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12951