Након много година истраживања и рада, као и безброј безуспешних покушаја проузрокованих непажљивим програмерима који у коду који покреће свемирски брод грешком оставе команду system("PAUSE"), а неретко и readln(), прва људска експедиција је успешно слетела на Марс! Чим су слетели, мала Марина, вођа експедиције, је приметила да се испред њих налази непомична колона у којој стоји \(n\) Марсоваца. На њено велико изненађење, Марсовци нису били зелени, већ металик розе боје.

Након неколико дана протеклих у збуњујућим покушајима комуникације, Марина је сазнала висине свих Mарсоваца (\(H_1 \dots H_N\)) и коначно је схватила да они непомично стоје јер тестирају интелигенцију нових посетилаца и желе да провере да ли ће Земљани успети да наћу подниз узастопних Марсоваца из колоне, такав да је разлика највишег и најнижег Марсовца највећа могућа.

Како је овај проблем Марини превише једноставан, одлучила је да додатно импресионира нове познанике тако што ће им рећи колико таквих поднизова постоји. Помозите Марини да обори Марсовце с ногу и започне једно ново пријатељство.

Опис улаза

У првој линији стандардног улаза налази се један природан број \(N\) - број Марсоваца у колони. У другој линији стандардног улаза налази се \(N\) природних бројева, \(H_1 \dots H_N\) - висине Марсоваца (у метрима) редом, од првог до последњег у колони.

Опис излаза

У првом и једином реду стандардног излаза исписати један ненегативан цео број који представља број начина да се одабере подниз узастопних Марсоваца такав да је разлика највишег и најнижег међу њима највећа могућа.

Примери

<div class="panel panel-default">
    <div class="panel-heading">
        <span class="pull-left" style="width: 48%;">Ulaz</span>
        <span style="padding-left: 15px;">Izlaz</span>
    </div>
    <div class="panel-body">
        <span class="pull-left exampleinput">
            5<br/>
            3 5 2 1 4
        </span>
        <span class="exampleoutput">
            4
        </span>
    </div>
</div>

<div class="panel panel-default">
    <div class="panel-heading">
        <span class="pull-left" style="width: 48%;">Ulaz</span>
        <span style="padding-left: 15px;">Izlaz</span>
    </div>
    <div class="panel-body">
        <span class="pull-left exampleinput">
            2<br/>
            21 8
        </span>
        <span class="exampleoutput">
            1
        </span>
    </div>
</div>

Објашњење примера

У првом примеру највећа могућа разлика између највишег и најнижег Марсовца у неком поднизу је 4 метра и може се добити на 4 различита начина, и то ако одаберемо неки од наредних поднизова:

• од првог до четвртог Марсовца, тј. \([3, 5, 2, 1]\)
• од другог до петог Марсовца, тј. \([5, 2, 1, 4]\)
• од првог до петог Марсовца, тј. \([3, 5, 2, 1, 4]\)
• од другог до четвртог Марсовца, тј. \([5, 2, 1]\)

У другом примеру највећа могућа разлика је 13 метара и може се добити само ако у подниз укључимо оба Марсовца.

Ограничења

• \(1 \leq Hi \leq 10^9\).

Тест примери су подељени у четири дисјунктне групе:

• У тест примерима који вреде 15 поена важи \(1 \leq N \leq 100\).
• У тест примерима који вреде 20 поена важи \(1 \leq N \leq 3000\).
• У тест примерима који вреде 15 поена не постоје два Марсовца исте висине и важи \(1 \leq N \leq 10^5\).
• У тест примерима који вреде 50 поена важи \(1 \leq N \leq 10^5\).

Напомена

Обратите пажњу да је за решење потребно користити \(64\)-битни тип података.