산

펭귄 펭구는 남극에서 펭귄 친구들과 함께 살고 있다. 날지 못하는 새들이지만, 이들은 하늘을 나는 기쁨을 느끼고 싶어 한다. 펭구는 기술의 힘, 즉 글라이더로 친구들의 소원을 이루어 주기로 한다.

다행히도 펭구가 사는 남극 횡단 산맥에는 n개의 산이 있다. 산에는 1부터 n까지 번호가 붙어 있고 왼쪽에서 오른쪽으로 한 줄로 늘어서 있다. i번째 산의 높이는 Hi이다.

펭구는 세 산 x, y, z를 고르기로 한다. 산 y에는 기지국을, 산 x와 z에는 수신소를 세울 계획이다. 펭귄들은 산 y에서 산 x 또는 z로 활강한다. 공중 충돌을 피하면서 더 많은 펭귄을 수용하기 위해, 산 x는 산 y의 왼쪽에, 산 z는 산 y의 오른쪽에 있다. 또한 산 x와 z는 산 y보다 반드시 낮아야 한다. 펭구는 꼼꼼하기 때문에 가능한 모든 선택을 고려하려고 한다. 1 ≤ x < y < z ≤ n, Hx < Hy, Hy > Hz를 만족하는 (x, y, z)의 가능한 선택의 수를 구하라.

프로그램은 표준 입력에서 읽는다. 첫째 줄에는 산의 개수 n이 주어진다. 둘째 줄에는 n개의 정수가 주어지며, i번째 정수는 i번째 산의 높이 Hi이다.

프로그램은 표준 출력에 출력한다.

출력은 한 줄에 하나의 정수로, (x, y, z)의 가능한 선택의 총 개수이다.

• 3 ≤ n ≤ 3 × 105
• 0 ≤ Hi ≤ 1018