Podciągi arytmetyczne

Limit pamięci: 32 MB

Masz podaną pewną permutację liczb dla pewnego . Niech kolejne liczby permutacji tworzą ciąg . Twoim zadaniem jest policzenie, ile istnieje arytmetycznych podciągów ciągu o długości równej 3. Dokładniej, musisz zliczyć trójki takie że oraz .

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita . Drugi wiersz zawiera liczb całkowitych , reprezentujących naszą permutację.

Możesz założyć, że w testach wartych przynajmniej punktów zachodzi dodatkowy warunek .

Wyjście

Na wyjściu należy wypisać liczbę podciągów arytmetycznych o długości 3 dla permutacji z wejścia. Możesz założyć, że wynik nie przekroczy .

Przykład

Dla danych wejściowych:

5
1 5 4 2 3

poprawną odpowiedzią jest:

2

Autor zadania: Adrian Jaskółka.