Jim has invented a new flying object called HZ42. HZ42 is like a broom and can only fly horizontally, independent of the environment. One day, Jim started his flight from Dubai's highest skyscraper, traveled some distance and landed on another skyscraper of same height! So much fun! But unfortunately, new skyscrapers have been built recently.

Let us describe the problem in one dimensional space. We have in total $N$ skyscrapers aligned from left to right. The $\boldsymbol{i}$^{th} skyscraper has a height of $h_i$. A flying route can be described as $(i,j)$ with $i\neq j$, which means, Jim starts his HZ42 at the top of the skyscraper $\boldsymbol{i}$ and lands on the skyscraper $j$. Since HZ42 can only fly horizontally, Jim will remain at the height $h_i$ only. Thus the path $(i,j)$ can be valid, only if each of the skyscrapers $i,i+1,\ldots,j-1,j$ is not strictly greater than $h_i$ and if the height of the skyscraper he starts from and arrives on have the same height. Formally, $(i,j)$ is valid iff $\nexists k\in[i,j]:h_k>h_i$ and $h_i=h_j$.

Help Jim in counting the number of valid paths represented by ordered pairs $(i,j)$.  

Input Format

The first line contains $N$, the number of skyscrapers. The next line contains $N$ space separated integers representing the heights of the skyscrapers. 

Output Format

Print an integer that denotes the number of valid routes.

Constraints

$1\leq N\leq3\cdot10^5$ and no skyscraper will have height greater than $10^{6}$ and less than $\mbox{1}$.

Sample Input #00

6
3 2 1 2 3 3

Sample Output #00

8

Sample Input #01

3
1 1000 1

Sample Output #01

0

Explanation

First testcase: (1, 5), (1, 6) (5, 6) and (2, 4) and the routes in the opposite directions are the only valid routes. 

Second testcase: (1, 3) and (3, 1) could have been valid, if there wasn't a big skyscraper with height 1000 between them.

Source: hackerrank | Difficulty: MEDIUM
Tags: Data structures


Solutions:
n = int(input())
hs = map(int, input().split())
hhs = sorted(enumerate(hs), key=lambda t: (t[1], t[0]))
prev = list(range(-1, n - 1))
next = list(range(1, n + 1))
(firsti, firsth) = (lasti, lasth) = hhs[0]
block_len = 1
s = 0
for (i, h) in hhs[1:]:
	if h == lasth and i == next[lasti]:
		block_len += 1
		lasti = i
	else:
		s += block_len * (block_len - 1)
		(pi, ni) = (prev[firsti], next[lasti])
		if pi >= 0:
			next[pi] = ni
		if ni < n:
			prev[ni] = pi
		(firsti, firsth) = (lasti, lasth) = (i, h)
		block_len = 1
s += block_len * (block_len - 1)
print(s)


N = int(input())
h = [int(i) for i in input().split()]
count = 0
s = []
for i in range(0, N):
	while len(s) > 0 and s[-1][0] < h[i]:
		s.pop()
	if len(s) > 0 and s[-1][0] == h[i]:
		count += s[-1][1]
		s[-1][1] += 1
	else:
		s.append([h[i], 1])
print(2 * count)


def bin_search(arr, low, high, item):
	while low <= high:
		mid = low + (high - low) // 2
		if arr[mid][0] == item:
			return mid
		elif arr[mid][0] < item:
			high = mid - 1
		else:
			low = mid + 1
	return low

def calc(heights):
	available = []
	last_available = -1
	count = 0
	for height in heights:
		idx = bin_search(available, 0, last_available, height)
		if idx > last_available:
			new_available = [height, 1]
			if len(available) == idx:
				available.append(new_available)
			else:
				available[idx] = new_available
		elif available[idx][0] == height:
			count += available[idx][1]
			available[idx][1] += 1
		else:
			available[idx] = [height, 1]
		last_available = idx
	return count * 2
n = input()
print(calc((int(value) for value in input().split())))


class Interval:

	def __init__(self, start, end, number, count):
		self.start = start
		self.end = end
		self.number = number
		self.count = count
		self.parent = None
		self.left = None
		self.right = None

	def __str__(self):
		return '({0}, {1}, {2}, {3})'.format(self.start, self.end, self.number, self.count)

class IntervalsManager:

	def __init__(self, n):
		self.intervals = [None for i in range(0, n)]
		self.n = n
		self.counter = 0

	def insert_point(self, index, number):
		if index > 0 and self.intervals[index - 1] is not None:
			interval = self.intervals[index - 1]
			self.intervals[index] = interval
			interval.end = index
			if interval.number == number:
				self.counter = self.counter + 2 * interval.count
				interval.count = interval.count + 1
			else:
				interval.number = number
				interval.count = 1
		else:
			self.intervals[index] = Interval(index, index, number, 1)
		if index < self.n - 1 and self.intervals[index + 1] is not None:
			interval = self.intervals[index]
			interval_right = self.intervals[index + 1]
			interval.end = interval_right.end
			self.intervals[interval_right.end] = interval

	def print(self):
		for i in range(0, n):
			print(self.intervals[i])
n = int(input())
array = [int(x) for x in input().split()]
custom_array = sorted([(n, i) for (i, n) in enumerate(array)])
intervalsManager = IntervalsManager(n)
for i in range(0, n):
	(number, index) = custom_array[i]
	intervalsManager.insert_point(index, number)
print(intervalsManager.counter)


import sys

def getPathsNum(heights):
	current_result = {'num': 1, 'path_num': 0, 'pos': 0}
	result_stack = []
	i = 1
	while i < len(heights):
		if heights[i] == heights[current_result['pos']]:
			current_result['num'] = current_result['num'] + 1
			i = i + 1
		elif heights[i] < heights[current_result['pos']]:
			result_stack.append(current_result)
			current_result = {'num': 1, 'path_num': 0, 'pos': i}
			i = i + 1
		elif len(result_stack):
			new_result = result_stack.pop()
			new_result['path_num'] = new_result['path_num'] + current_result['path_num'] + pow(current_result['num'], 2) - current_result['num']
			current_result = new_result
		else:
			current_result['path_num'] = current_result['path_num'] + pow(current_result['num'], 2) - current_result['num']
			current_result['pos'] = i
			current_result['num'] = 1
			i = i + 1
	path_num = current_result['path_num'] + pow(current_result['num'], 2) - current_result['num']
	for result in result_stack:
		path_num = path_num + result['path_num'] + pow(result['num'], 2) - result['num']
	return path_num
sys.stdin.readline()
print(getPathsNum(list(map(int, sys.stdin.readline().split()))))


input()
heights = list(map(int, input().split()))
hs = [9 ** 9] * 300000
ns = [0] * 300000
i = 0
count = 0
for height in heights:
	while height > hs[i]:
		i -= 1
	if height < hs[i]:
		i += 1
		hs[i] = height
		ns[i] = 1
	else:
		count += ns[i]
		ns[i] += 1
print(2 * count)


l = int(input())
a = [int(x) - 1 for x in input().split()]
maxh = max(a)
h = [0 for x in range(maxh + 1)]
result = 0
prev = maxh + 1
if len(set(a)) > 20000:
	for curr in a:
		if curr > prev:
			h[prev:curr] = [0 for _ in range(curr - prev)]
		result += h[curr]
		h[curr] += 1
		prev = curr
else:
	nonZero = set()
	for curr in a:
		if curr > prev:
			for i in list(nonZero):
				if prev <= i < curr:
					nonZero.remove(i)
					h[i] = 0
		result += h[curr]
		h[curr] += 1
		nonZero.add(curr)
		prev = curr
print(result * 2)


HEIGHT = 'height'
COUNT = 'count'

def compute_num_paths(heights):
	total_paths = 0
	height_stack = []
	for i in heights:
		while len(height_stack) and height_stack[-1][HEIGHT] < i:
			count = height_stack.pop()[COUNT]
			total_paths += count * (count - 1)
		if len(height_stack) == 0 or height_stack[-1][HEIGHT] > i:
			height_stack.append({HEIGHT: i, COUNT: 1})
		elif height_stack[-1][HEIGHT] == i:
			height_stack[-1][COUNT] += 1
	while len(height_stack):
		count = height_stack.pop()[COUNT]
		total_paths += count * (count - 1)
	return total_paths
input()
heights = map(int, input().split(' '))
print(compute_num_paths(heights))


class Stack(object):

	def __init__(self):
		self.data = []

	def push(self, data):
		self.data.append(data)

	def pop(self):
		if not len(self.data):
			return None
		return self.data.pop()

	def peek(self):
		if not len(self.data):
			return None
		return self.data[-1]

	def size(self):
		return len(self.data)

def horizontal_routes(heights):
	stack = Stack()
	count = 0
	for height in heights:
		top_of_stack = stack.peek()
		while top_of_stack and top_of_stack[0] < height:
			stack.pop()
			top_of_stack = stack.peek()
		if top_of_stack:
			if top_of_stack[0] == height:
				top = stack.pop()
				count += top[1]
				updated = (height, top[1] + 1)
				stack.push(updated)
			else:
				stack.push((height, 1))
		else:
			stack.push((height, 1))
	return count * 2
number_of_heights = int(input())
heights = (int(x) for x in input().split())
print(horizontal_routes(heights))


N = int(input())
arr = list(map(int, input().split()))
ans = 0
ma = [(10 ** 9, 1)]
for i in range(len(arr) - 1, -1, -1):
	if arr[i] < ma[-1][0]:
		ma.append((arr[i], 1))
	else:
		while arr[i] > ma[-1][0]:
			ma.pop(-1)
		if arr[i] == ma[-1][0]:
			(c, v) = ma.pop(-1)
			ans += v * 2
			ma.append((c, v + 1))
		else:
			ma.append((arr[i], 1))
print(ans)


import heapq
count = int(input())
values = [int(n) for n in input().split()]
dic = {}
total = 0
heap = []

def calc(val):
	return val * (val + 1) // 2 * 2
for value in values:
	if len(heap) != 0:
		if heap[0] < value:
			while True:
				if len(heap) == 0:
					break
				if heap[0] >= value:
					break
				val = heapq.heappop(heap)
				dicval = dic[val]
				del dic[val]
				if dicval > 1:
					total = total + calc(dicval - 1)
	if value in dic:
		dic[value] = dic[value] + 1
		if len(heap) == 0:
			heapq.heappush(heap, value)
	else:
		dic[value] = 1
		heapq.heappush(heap, value)
for i in heap:
	if i in dic:
		dicval = dic[i]
		if dicval > 1:
			total = total + calc(dic[i] - 1)
print(total)


from itertools import takewhile
from operator import add
from math import factorial

def parse_heights(heights_str):
	return [int(height) for height in heights_str.strip().split()]

def peek(stack):
	return stack[-1]

def calc_n_paths(heights):
	height_stack = []
	n_paths = 0
	for height in heights:
		if len(height_stack) < 1:
			height_stack.append(height)
			continue
		while height_stack and peek(height_stack) < height:
			n_paths += drain_and_calc_n_paths(height_stack)
		height_stack.append(height)
	while height_stack:
		n_paths += drain_and_calc_n_paths(height_stack)
	return n_paths

def drain_and_calc_n_paths(height_stack):
	n_at_same_height = drain_top_of_stack(height_stack)
	return calculate_num_combinations(n_at_same_height, 2) * 2

def drain_top_of_stack(height_stack):
	top = peek(height_stack)
	n_at_same_height = 0
	while height_stack and peek(height_stack) == top:
		n_at_same_height += 1
		height_stack.pop()
	return n_at_same_height

def calculate_num_combinations(n, k):
	if n < k:
		return 0
	return int(factorial(n) / (factorial(k) * factorial(n - k)))

def main():
	n_skyscrapers = int(input())
	heights = parse_heights(input())
	print(calc_n_paths(heights))
main()


n = int(input())
height = list(map(int, input().split()))
ans = 0
seen = []
times = {}
for i in height:
	if len(seen) == 0:
		seen.append(i)
		times[i] = 1
	elif seen[len(seen) - 1] == i:
		times[i] += 1
	elif seen[len(seen) - 1] > i:
		seen.append(i)
		if i in times:
			times[i] += 1
		else:
			times[i] = 1
	else:
		while len(seen) != 0 and seen[len(seen) - 1] < i:
			temp = seen.pop()
			ans += times[temp] * (times[temp] - 1)
			times[temp] = 0
		if len(seen) == 0:
			seen.append(i)
		elif seen[len(seen) - 1] != i:
			seen.append(i)
		if i in times:
			times[i] += 1
		else:
			times[i] = 1
while len(seen) != 0:
	temp = seen.pop()
	ans += times[temp] * (times[temp] - 1)
print(ans)


N = int(input())
h = [int(i) for i in input().split()]
count = 0
s = []
for i in range(0, N):
	while len(s) > 0 and s[-1][0] < h[i]:
		s.pop()
	if len(s) > 0 and s[-1][0] == h[i]:
		count += s[-1][1]
		s[-1][1] += 1
	else:
		s.append([h[i], 1])
print(2 * count)


def main():
	numSkyscrapers = int(input())
	hs = input().split()
	heights = list(map(lambda x: int(x), hs))
	currentHeight = heights[0]
	prevVals = verts = [None] * numSkyscrapers
	prevValIndex = 0
	counts = [None] * numSkyscrapers
	tsum = 0
	for y in range(0, len(heights)):
		h = heights[y]
		while prevValIndex > 0 and prevVals[prevValIndex - 1] < h:
			prevValIndex -= 1
		if prevValIndex > 0 and h == prevVals[prevValIndex - 1]:
			tsum += counts[prevValIndex - 1]
			counts[prevValIndex - 1] += 1
		else:
			prevVals[prevValIndex] = h
			counts[prevValIndex] = 1
			prevValIndex += 1
	print(tsum * 2)
main()


from heapq import *
n = int(input())
count = 0
heights = []
for height in map(int, input().split()):
	(h, c) = (0, 0)
	while len(heights) > 0:
		(h, c) = heights[0]
		if h < height:
			heappop(heights)
		else:
			break
	if h == height:
		count += 2 * c
		heappushpop(heights, (h, c + 1))
	else:
		heappush(heights, (height, 1))
print(count)


N = int(input())
heights = [int(x) for x in input().split()]
hstack = []
ret = 0
for hcurr in heights:
	dup = 0
	while hstack and hstack[-1][0] <= hcurr:
		(hprev, duprev) = hstack.pop()
		if hprev == hcurr:
			dup += 1 + duprev
	hstack.append((hcurr, dup))
	ret += dup * 2
print(ret)


from collections import deque

def trinum(num):
	return int(num * (num - 1) / 2)

def main():
	numbers = deque()
	input()
	buildings = list(map(int, input().split()))
	total = 0
	for building in buildings:
		try:
			top = numbers.pop()
			while top[0] < building:
				total += trinum(top[1])
				top = numbers.pop()
			if top[0] == building:
				top[1] += 1
				numbers.append(top)
			else:
				numbers.append(top)
				numbers.append([building, 1])
		except IndexError:
			numbers.append([building, 1])
	for num in numbers:
		total += trinum(num[1])
	print(total * 2)
main()


from collections import deque
N = int(input())
S = [int(x) for x in input().split()]
paths = 0
levels = deque()
(comp, mult) = (S[0], 1)
i = 1
while i < N:
	cur = S[i]
	if cur < comp:
		levels.append((comp, mult))
		(comp, mult) = (cur, 1)
		i += 1
	elif cur > comp:
		if len(levels) > 0:
			(comp, mult) = levels.pop()
		else:
			(comp, mult) = (cur, 1)
			i += 1
	else:
		paths += mult
		mult += 1
		i += 1
print(2 * paths)


N = int(input())
a = list(map(int, input().split()))
res = 0
stack = [(a[0], 1)]
for value in a[1:]:
	count = 1
	while stack and value >= stack[-1][0]:
		(prev_value, prev_count) = stack.pop()
		if prev_value == value:
			count += prev_count
		else:
			res += prev_count * (prev_count - 1) // 2
	stack.append((value, count))
for (val, count) in stack:
	res += count * (count - 1) // 2
print(2 * res)


def routesForward(skyscrapers, size):
	count = 0
	for i in range(0, size):
		for j in range(i + 1, size):
			if skyscrapers[j] > skyscrapers[i]:
				break
			elif skyscrapers[j] == skyscrapers[i]:
				count += 1
	return count

def routesWithStack(skyscrapers, size):
	count = 0
	stack = []
	for i in range(0, size):
		while len(stack) != 0 and skyscrapers[i] > stack[-1][0]:
			item = stack.pop()
			if item[1] > 1:
				count += item[1] * (item[1] - 1)
		if len(stack) != 0 and skyscrapers[i] == stack[-1][0]:
			stack[-1][1] += 1
		else:
			stack.append([skyscrapers[i], 1])
	for i in stack:
		count += i[1] * (i[1] - 1)
	return count
numSkyscrapers = int(input())
skyscrapers = list(map(int, input().split()))
print(routesWithStack(skyscrapers, numSkyscrapers))


L = {}
(lines, nums, types) = (input(), list(map(int, input().split(' '))), [])
for i in nums:
	if not i in L.keys():
		L[i] = [0]
	L[i][-1] += 1
	while len(types) != 0 and types[-1] < i:
		L[types[-1]] += [0]
		del types[-1]
	if len(types) == 0 or i < types[-1]:
		types += [i]
total = 0
for i in L.keys():
	total += int(sum(map(lambda x: x * (x - 1) / 2, L[i]))) * 2
print(total)


N = int(input())
heights = list(map(int, input().split(' ')))
total = 0
size = 0
v = [0] * N
m = [0] * N
for i in range(N):
	h = heights[i]
	while size > 0 and v[size - 1] < h:
		size -= 1
	if size < 1 or v[size - 1] > h:
		v[size] = h
		m[size] = 0
		size += 1
	total += m[size - 1]
	m[size - 1] += 1
print(total * 2)


num_ss = int(input())
heights = list(reversed(list(map(int, input().split()))))
stack = []
num_paths = 0
for x in range(0, num_ss):
	height = heights.pop()
	if stack and stack[len(stack) - 1] < height:
		old = stack.pop()
		c = 1
		while stack and stack[len(stack) - 1] < height:
			new = stack.pop()
			if new == old:
				c = c + 1
			else:
				num_paths = num_paths + c * (c - 1)
				old = new
				c = 1
		num_paths = num_paths + c * (c - 1)
	stack.append(height)
while stack:
	old = stack.pop()
	c = 1
	while stack and stack[len(stack) - 1] == old:
		c = c + 1
		stack.pop()
	num_paths = num_paths + c * (c - 1)
print(num_paths)


import fileinput
import math
lines = [line.strip() for line in fileinput.input()]
skyscrapers = int(lines[0])
height = lines[1].split(' ')
count = 0
temp_stack = []
height = [int(h) for h in height]
if skyscrapers < 2:
	print(count)
else:
	temp_stack.append((height[0], 1))
	for h in height[1:]:
		while temp_stack and h > temp_stack[-1][0]:
			if temp_stack[-1][1] > 1:
				count = count + temp_stack[-1][1] * (temp_stack[-1][1] - 1)
			temp_stack.pop()
		if temp_stack and h == temp_stack[-1][0]:
			value = temp_stack[-1][1] + 1
			temp_stack.pop()
			temp_stack.append((h, value))
		else:
			temp_stack.append((h, 1))
	for x in temp_stack:
		count = count + x[1] * (x[1] - 1)
	print(count)


class Building(object):

	def __init__(self, height, routes):
		self.height = height
		self.routes = routes
n = int(input())
skyscrapers = [int(x) for x in input().split()]
buildings = []
total_routes = 0
for height in skyscrapers:
	while buildings and buildings[-1].height < height:
		buildings.pop()
	if not buildings or buildings[-1].height > height:
		buildings.append(Building(height, 0))
	total_routes += buildings[-1].routes
	buildings[-1].routes += 1
print(total_routes * 2)


a = [(0, 0)] * int(input())
(c, l) = (0, 1)
for i in map(int, input().split()):
	if a[0][0] < i:
		a[0] = (i, 1)
		l = 1
	else:
		(mid, step) = (0, 1 << l.bit_length())
		while step:
			step >>= 1
			if mid + step < l and a[mid + step][0] >= i:
				mid += step
		l = mid + 1
		if a[l - 1][0] == i:
			c += a[l - 1][1]
			a[l - 1] = (a[l - 1][0], a[l - 1][1] + 1)
		else:
			a[l] = (i, 1)
			l += 1
print(2 * c)


READ_FROM_FILE = False
if READ_FROM_FILE:
	inp = open('input.txt').readline
else:
	inp = input
n = int(inp().strip())
skyscrapers = list(map(int, inp().strip().split()))
paths_count = 0
size = 0
heights = [0] * n
amounts = [0] * n
for skyscraper in skyscrapers:
	while size > 0 and heights[size - 1] < skyscraper:
		size -= 1
	if size < 1 or heights[size - 1] > skyscraper:
		heights[size] = skyscraper
		amounts[size] = 0
		size += 1
	paths_count += amounts[size - 1]
	amounts[size - 1] += 1
print(paths_count * 2)


import collections
import bisect

def check(h):
	matches = 0
	stack = collections.deque()
	for x in h:
		if not stack:
			stack.appendleft(x)
		else:
			if x >= stack[0]:
				while stack and stack[0] < x:
					stack.popleft()
				matches = matches + bisect.bisect_right(stack, x)
			stack.appendleft(x)
	return matches
N = int(input())
h = [int(x) for x in input().split()]
print(2 * check(h))


N = int(input().strip())
heights = [int(h) for h in input().strip().split()]
count = 0
starts = []
for i in range(len(heights)):
	while len(starts) > 0 and heights[i] > starts[-1][0]:
		starts.pop()
	if len(starts) > 0 and heights[i] == starts[-1][0]:
		count += starts[-1][1]
		starts[-1][1] += 1
	else:
		starts.append([heights[i], 1])
print(2 * count)


N = int(input().strip())
scrapers = [int(num) for num in input().strip().split()]

def unwind(stack, scraper):
	flights = 0
	current = stack.pop()
	times = 1
	while len(stack) > 0:
		if stack[-1] >= scraper:
			flights += times * (times - 1)
			stack.append(scraper)
			return flights
		if stack[-1] > current:
			flights += times * (times - 1)
			current = stack.pop()
			times = 1
			continue
		times += 1
		stack.pop()
	flights += times * (times - 1)
	stack.append(scraper)
	return flights
stack = []
flights = 0
for scraper in scrapers:
	if len(stack) == 0:
		stack.append(scraper)
		continue
	if scraper <= stack[-1]:
		stack.append(scraper)
		continue
	flights += unwind(stack, scraper)
flights += unwind(stack, 1000000.0 + 1)
print(flights)


_ = int(input())
st = []
tot = 0
for x in (int(s) for s in input().split()):
	while st and st[-1][0] < x:
		st.pop()
	if st and st[-1][0] == x:
		tot += st[-1][1] * 2
		st[-1][1] += 1
	else:
		st.append([x, 1])
print(tot)


import sys
import math
N = int(input())
skyscrappers = [int(x) for x in str(input()).strip().split(' ')]
st = []
total = 0

def nC2(n):
	return n * (n - 1) / 2
for (i, x) in enumerate(skyscrappers):
	if st:
		top = st[-1]
		if x <= top:
			st.append(x)
		else:
			hold_on = st.pop()
			t = 1
			while st and x > st[-1]:
				top = st.pop()
				if top == hold_on:
					t += 1
				else:
					if t > 1:
						total += nC2(t)
					hold_on = top
					t = 1
			if t > 1:
				total += nC2(t)
			st.append(x)
	else:
		st.append(x)
hold_on = st.pop()
t = 1
while st:
	top = st.pop()
	if top == hold_on:
		t += 1
	else:
		if t > 1:
			total += nC2(t)
		t = 1
		hold_on = top
if t > 1:
	total += nC2(t)
print(int(total * 2))


N = int(input())
H = list(map(int, input().split(' ')))
stack = []
count = 0
for n in range(0, N):
	incr = False
	while len(stack) > 0:
		h = stack[-1]
		if H[n] > h[0]:
			stack.pop()
		else:
			if H[n] == h[0]:
				count += h[1]
				incr = True
			break
	if incr:
		stack[-1] = (H[n], stack[-1][1] + 1)
	else:
		stack.append((H[n], 1))
print(2 * count)


def countTot(di):
	count = 0
	for (k, v) in di.items():
		count += v * (v - 1)
	return count
n = int(input())
arr = list(map(int, input().strip().split(' ')))
stack = []
di = {}
tot = 0
for a in arr:
	while len(stack) > 0 and stack[-1] < a:
		z = stack.pop()
		if z not in di:
			di[z] = 0
		di[z] += 1
	tot += countTot(di)
	di = {}
	stack.append(a)
di = {}
for a in stack:
	if a not in di:
		di[a] = 0
	di[a] += 1
print(tot + countTot(di))


n = int(input())
arr = [int(x) for x in input().split()]
stack = []
ans = 0
i = 0
while i < n:
	if stack:
		if arr[i] > stack[-1]:
			cur = stack[-1]
			cnt = 0
			while stack:
				if stack[-1] == cur:
					stack.pop()
					cnt += 1
				else:
					break
			ans += (cnt > 1) * (cnt - 1) * cnt
		else:
			stack.append(arr[i])
			i += 1
	else:
		stack = [arr[i]]
		i += 1
while stack:
	cur = stack[-1]
	cnt = 0
	while stack:
		if stack[-1] == cur:
			stack.pop()
			cnt += 1
		else:
			break
	ans += (cnt > 1) * (cnt - 1) * cnt
print(ans)


import math

def right(i):
	return 2 * i + 1

def left(i):
	return 2 * i + 2

def parent(i):
	return math.ceil(i / 2) - 1

def heapify(ar, i, ln, compare):
	if i >= ln:
		return
	largest = i
	l = left(i)
	r = right(i)
	if l < ln and compare(ar[l], ar[largest]):
		largest = l
	if r < ln and compare(ar[r], ar[largest]):
		largest = r
	if largest != i:
		temp = ar[i]
		ar[i] = ar[largest]
		ar[largest] = temp
		heapify(ar, largest, ln, compare)

def maxheapify(ar, i, ln):
	return heapify(ar, i, ln, lambda x, y: x > y)

def minheapify(ar, i, ln):
	return heapify(ar, i, ln, lambda x, y: x < y)

def heapsort(ar):
	l = len(ar)
	p = parent(l - 1)
	for i in reversed(range(p + 1)):
		minheapify(ar, i, l)

class Heap:

	def __init__(self, compare, heap=None):
		self.__size = 0
		self.__compare = compare
		if heap == None:
			self.__heap = []
		else:
			self.__heap = heap
			self.__size = len(heap)

	def pop(self):
		if self.isempty():
			raise 'Heap is empty.'
		val = self.__heap[0]
		self.__size -= 1
		if self.__size > 0:
			self.__heap[0] = self.__heap[self.__size]
			heapify(self.__heap, 0, self.__size, self.__compare)
		return val

	def push(self, item):
		if self.__size >= len(self.__heap):
			self.__heap.append(item)
		else:
			self.__heap[self.__size] = item
		i = parent(self.__size)
		self.__size += 1
		while i >= 0:
			heapify(self.__heap, i, self.__size, self.__compare)
			i = parent(i)

	def peek(self):
		return self.__heap[0]

	def isempty(self):
		return self.__size == 0

	def size(self):
		return self.__size

def flightpaths(buildings):
	launchpads = {}
	minheap = Heap(lambda x, y: x < y)
	paths = 0
	for b in buildings:
		while not minheap.isempty() and minheap.peek() < b:
			toosmall = minheap.pop()
			launchpads.pop(toosmall)
		if b in launchpads:
			paths += launchpads[b]
			launchpads[b] += 1
		else:
			launchpads[b] = 1
			minheap.push(b)
	return paths * 2
input()
print(flightpaths(list(map(lambda x: int(x), input().split(' ')))))


n = int(input())
H = list(map(int, input().split()))
(size, sum1) = (0, 0)
(V, M) = ([0] * n, [0] * n)
for i in range(n):
	h = H[i]
	while size > 0 and V[size - 1] < h:
		size -= 1
	if size < 1 or V[size - 1] > h:
		(V[size], M[size]) = (h, 0)
		size += 1
	sum1 += M[size - 1]
	M[size - 1] += 1
print(sum1 << 1)


n = int(input().strip())
m = 1000000
h = list(map(int, input().strip().split()))
h.append(m + 1)
r = [0] * n
for i in range(n - 1, -1, -1):
	t = i + 1
	while h[i] >= h[t]:
		t = r[t]
	r[i] = t
f = []
for i in range(m + 1):
	f.append([])
for i in range(n):
	f[h[i]].append(i)
ans = 0
for i in range(m + 1):
	t = 0
	for j in range(len(f[i]) - 1):
		if r[f[i][j]] > f[i][j + 1]:
			t += 1
		else:
			ans += t * (t + 1) // 2
			t = 0
	ans += t * (t + 1) // 2
print(ans * 2)


from collections import defaultdict
N = int(input().strip())
harr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
d = defaultdict(list)
for i in range(N):
	d[harr[i]].append(i)
total = 0
jump = defaultdict(lambda : None)
for (h, a) in sorted(d.items()):
	group = 1
	sai = 0
	ni = 1
	i = a[0] + 1
	while i <= a[-1]:
		if harr[i] > h:
			total += group * (group - 1)
			jump[a[sai]] = i - 1
			group = 1
			i = a[ni] + 1
			sai = ni
			ni += 1
		elif i == a[ni]:
			group += 1
			ni += 1
			i += 1
		elif jump[i] is not None:
			i = jump[i] + 1
		else:
			i += 1
	total += group * (group - 1)
	jump[a[sai]] = i - 1
print(total)


import sys
from math import factorial

def binomial(n, k):
	if n == k:
		return 1
	elif k == 1:
		return n
	elif k > n:
		return 0
	a = factorial(n)
	b = factorial(k)
	c = factorial(n - k)
	return a // (b * c)
n = int(input().strip())
H = [int(h) for h in input().strip().split(' ')]
H += [10 ** 6 + 1]
stack = []
count = 0
for h in H:
	while stack and h > stack[-1][0]:
		prev = stack.pop()
		if prev[1] > 0:
			count += binomial(prev[1] + 1, 2)
	if stack and h == stack[-1][0]:
		prev = stack.pop()
		stack.append((h, prev[1] + 1))
	else:
		stack.append((h, 0))
print(2 * count)


from itertools import groupby
import heapq
N = int(input())
hs = list(map(int, input().split()))

class Node(object):

	def __init__(self, h, idx):
		self.h = h
		self.idx = idx
		self.used = False
		(self.prev, self.next) = (None, None)
node_prev = None
nodes = []
for (idx, h) in enumerate(hs):
	n = Node(h, idx)
	if node_prev:
		node_prev.next = n
	n.prev = node_prev
	node_prev = n
	heapq.heappush(nodes, (h, idx, n))
cnt = 0
while nodes:
	(h, idx, node) = heapq.heappop(nodes)
	if node.used:
		continue
	path = [node]
	while node.next is not None:
		next_node = node.next
		if next_node.h != node.h:
			break
		path.append(next_node)
		node = next_node
	path_len = len(path)
	cnt += path_len * (path_len - 1) // 2
	for node in path:
		node_next = node.next
		node_prev = node.prev
		if node_prev:
			node_prev.next = node_next
		if node_next:
			node_next.prev = node_prev
		node.next = None
		node.prev = None
		node.used = True
print(2 * cnt)


st = [[float('inf'), 0]]
input()
res = 0
for h in map(int, input().split()):
	while st[-1][0] < h:
		st.pop()
	if st[-1][0] == h:
		res += st[-1][1]
		st[-1][1] += 1
	else:
		st.append([h, 1])
print(res * 2)


N = int(input())
A = [int(x) for x in input().split()]
height = [10 ** 7]
count = [1]
paths = 0
for h in A:
	while h > height[-1]:
		height.pop()
		count.pop()
	if h == height[-1]:
		paths += count[-1]
		count[-1] += 1
	else:
		height.append(h)
		count.append(1)
print(2 * paths)


n = int(input())
hs = map(int, input().split())
curr = []
count = 0
for i in range(n):
	h = hs.__next__()
	while len(curr) > 0 and h > curr[-1][0]:
		curr.pop()
	if len(curr) == 0:
		curr.append([h, 1])
	elif h == curr[-1][0]:
		count += curr[-1][1]
		curr[-1][1] += 1
	else:
		curr.append([h, 1])
print(count * 2)


from bisect import bisect_left

class StartPoint:

	def __init__(self, height, count=1):
		self.height = height
		self.count = count

	def __lt__(self, other):
		return self.height > other.height

def count_valid_routes(heights):
	result = 0
	start_points = []
	for h in heights:
		sp = StartPoint(h)
		i = bisect_left(start_points, sp)
		found = i < len(start_points) and start_points[i].height == h
		if found:
			result += 2 * start_points[i].count
		del_start = i + (1 if found else 0)
		del start_points[del_start:]
		if found:
			start_points[i].count += 1
		else:
			start_points.append(sp)
	return result
n = int(input())
heights = map(int, input().split())
print(count_valid_routes(heights))


n = int(input())
flights = []
count = 0
for height in input().split():
	height = int(height)
	while flights and flights[-1][0] < height:
		flights.pop()
	if flights and flights[-1][0] == height:
		count += flights[-1][1]
		flights[-1][1] += 1
	else:
		flights.append([height, 1])
print(count * 2)


n = int(input())
b = [[1000000000.0, 0]]
ans = 0
xx = [int(k) for k in input().split(' ')]
for x in xx:
	while b[-1][0] < x:
		b.pop()
	if b[-1][0] == x:
		ans += 2 * b[-1][1]
		b[-1][1] += 1
	else:
		b.append([x, 1])
print(ans)


import sys
heights = [int(x) for x in sys.stdin.readlines()[1].split()]

class Node:

	def __init__(self, value, frequency=1):
		(self.value, self.frequency) = (value, frequency)
(maxes, count) = ([], 0)
for height in heights:
	while len(maxes) > 0 and maxes[-1].value < height:
		maxes.pop()
	if len(maxes) > 0 and maxes[-1].value == height:
		count += maxes[-1].frequency
		maxes[-1].frequency += 1
	else:
		maxes.append(Node(height))
print(count * 2)


from heapq import heappop, heappush
from collections import defaultdict

def n_paths(heights):
	result = 0
	heap = []
	for (idx, val) in enumerate(heights, start=1):
		if not heap or val < heap[0][0]:
			heappush(heap, (val, 1))
		else:
			while heap and heap[0][0] < val:
				heappop(heap)
			if not heap:
				heappush(heap, (val, 1))
			else:
				(h_old, cnt) = heappop(heap)
				if h_old == val:
					result += cnt
					heappush(heap, (val, cnt + 1))
				else:
					heappush(heap, (h_old, cnt))
					heappush(heap, (val, 1))
	return 2 * result
_ = input()
heights = [int(x) for x in input().split()]
print(n_paths(heights))


from queue import PriorityQueue
from collections import defaultdict

def solve(heights):
	totals_dict = defaultdict(int)
	temp_dict = defaultdict(int)
	temp_queue = PriorityQueue()
	for h in heights:
		while temp_queue.queue and temp_queue.queue[0] < h:
			to_remove = temp_queue.get()
			count = temp_dict.pop(to_remove)
			if count > 1:
				totals_dict[to_remove] += count * (count - 1)
		if h not in temp_dict:
			temp_queue.put(h)
		temp_dict[h] += 1
	while temp_queue.queue:
		to_remove = temp_queue.get()
		count = temp_dict.pop(to_remove)
		if count > 1:
			totals_dict[to_remove] += count * (count - 1)
	print(sum(totals_dict.values()))
n = int(input())
heights = list(map(int, input().strip().split(' ')))
solve(heights)


n = int(input())
stack = []
heights = list(map(int, input().strip().split(' ')))
count = 0
for h in heights:
	while stack and stack[-1][0] < h:
		stack.pop()
	if stack and stack[-1][0] == h:
		count += stack[-1][1]
		stack[-1][1] += 1
	else:
		stack.append([h, 1])
print(count * 2)


class Node:

	def __init__(self, height=None, count=1, nodeAbove=None):
		self.h = height
		self.n = count
		self.up = nodeAbove

class ArrLinkedLists:

	def __init__(self):
		self.arr = [None] * 1001
		self.lowest = 1001

	def eat(self, h):
		iArr = h // 1000
		if iArr < self.lowest:
			self.lowest = iArr
			self.arr[iArr] = Node(h)
			return 0
		partial = 0
		while self.lowest < iArr:
			node = self.arr[self.lowest]
			self.arr[self.lowest] = None
			while node:
				partial += node.n * (node.n - 1)
				node = node.up
			self.lowest += 1
		node = self.arr[iArr]
		try:
			while node.h < h:
				partial += node.n * (node.n - 1)
				node = node.up
		except AttributeError:
			self.arr[iArr] = Node(h)
		else:
			if node.h > h:
				self.arr[iArr] = Node(h, 1, node)
			else:
				node.n += 1
				self.arr[iArr] = node
		return partial
ll = ArrLinkedLists()
nRoutes = 0
n = int(input().strip())
for h in map(int, input().split()):
	nRoutes += ll.eat(h)
nRoutes += ll.eat(1000001)
print(nRoutes)


import sys

class stack:

	def __init__(self):
		self.items = []

	def isEmpty(self):
		return self.items == []

	def push(self, item):
		self.items.append(item)

	def pop(self):
		return self.items.pop()

	def peek(self):
		return self.items[len(self.items) - 1]

	def size(self):
		return len(self.items)

	def __str__(self):
		d = ''
		for x in self.items:
			d += str(x) + ','
		return d

class info:

	def __init__(self, val, m, count):
		self.val = val
		self.m = m
		self.count = count

	def __str__(self):
		d = '(' + str(self.val) + ',' + str(self.m) + ',' + str(self.count) + ')'
		return d
n = int(sys.stdin.readline())
x = list(map(int, sys.stdin.readline().split()))
total_count = 0
s = stack()
s.push(info(x[0], 1, 0))
for i in range(1, n):
	while s.size() > 0 and x[i] > s.peek().val:
		y = s.pop()
		total_count += y.count
	if s.size() == 0 or x[i] < s.peek().val:
		s.push(info(x[i], 1, 0))
	elif x[i] == s.peek().val:
		top = s.peek()
		top.count += top.m
		top.m += 1
for obj in s.items:
	total_count += obj.count
print(2 * total_count)


import sys

def run(hs):
	n = 0
	cs = []
	for h in hs:
		while cs and cs[-1][0] < h:
			cs.pop()
		if cs and cs[-1][0] == h:
			n += cs[-1][1]
			cs[-1][1] += 1
		else:
			cs.append([h, 1])
	return n * 2

def main():
	n = input().strip().split(' ')
	hs = list(map(int, input().strip().split(' ')))
	print(run(hs))
main()


N = int(input())
heights = [int(x) for x in input().split()]
assert len(heights) == N
stack = []
result = 0
for h in heights:
	while len(stack) > 0 and stack[-1][0] < h:
		stack.pop()
	if len(stack) > 0 and stack[-1][0] == h:
		result += stack[-1][1]
		stack[-1] = (stack[-1][0], stack[-1][1] + 1)
	else:
		stack.append((h, 1))
print(2 * result)


class Stack:

	def __init__(self):
		self.items = []

	def isEmpty(self):
		return self.items == []

	def push(self, item):
		self.items.append(item)

	def pop(self):
		return self.items.pop()

	def peek(self):
		return self.items[len(self.items) - 1]

	def size(self):
		return len(self.items)

class Node:

	def __init__(self, data):
		self.data = data
		self.count = 1
n = int(input().strip())
stack = Stack()
arr = list(map(int, input().strip().split(' ')))
result = 0
for i in arr:
	while stack.size() > 0 and stack.peek().data < i:
		stack.pop()
	if stack.size() == 0 or stack.peek().data > i:
		stack.push(Node(i))
	else:
		tail = stack.peek()
		result += tail.count
		tail.count += 1
print(result * 2)


n = int(input())
heights = list(map(int, input().split(' ')))
answer = 0
routes = []
cur_heights = {}
for a in heights:
	if len(routes) == 0:
		routes.append(a)
		cur_heights[a] = 1
	elif routes[0] >= a:
		while routes[-1] < a:
			cur_heights[routes.pop()] -= 1
		routes.append(a)
		if a in cur_heights:
			answer += cur_heights[a]
			cur_heights[a] += 1
		else:
			cur_heights[a] = 1
	else:
		routes = [a]
		cur_heights = {a: 1}
print(2 * answer)


import sys

def solution(arr):
	res = 0
	st = []
	for ind in range(len(arr)):
		while st and st[-1][0] < arr[ind]:
			st.pop()
		if st and arr[ind] == st[-1][0]:
			res += st[-1][1]
			st[-1][1] += 1
		else:
			st.append([arr[ind], 1])
	return 2 * res
n = int(input().strip())
arr = [int(x) for x in input().strip().split()]
print(solution(arr))


def getans(a, v):
	le = -1
	lc = 0
	ans = 0
	while len(a) > 0 and a[-1] < v:
		e = a.pop()
		if e == le:
			lc += 1
		else:
			if lc > 1:
				ans += lc * (lc - 1)
			le = e
			lc = 1
	if lc > 1:
		ans += lc * (lc - 1)
	return ans
n = int(input())
l = list(map(int, input().split(' ')))
a = []
ans = 0
for v in l:
	ans += getans(a, v)
	a.append(v)
ans += getans(a, 10000000)
print(ans)


import sys
from time import time
import bisect

def solve_slow(hh):

	def get_cache(hh):
		cache = dict()
		for (i, h) in enumerate(hh):
			if h in cache:
				cache[h].append(i)
			else:
				cache[h] = [i]
		return cache

	def gen(hh, cache, fr, to, mn, mx):
		stack = [(fr, to, mn, mx)]
		while stack:
			(fr, to, mn, mx) = stack.pop()
			h = None
			for i in range(mx, mn - 1, -1):
				if i in cache:
					points = cache[i]
					ix1 = bisect.bisect_left(points, fr)
					ix2 = bisect.bisect_right(points, to)
					if ix1 != ix2:
						h = i
						break
			if h is not None:
				sm = (ix2 - ix1) * (ix2 - ix1 - 1)
				yield (fr, to, h, sm)
				(new_fr, new_to) = (fr, points[ix1])
				if new_fr != new_to:
					stack.append((new_fr, new_to, mn, h - 1))
				for i in range(ix1 + 1, ix2):
					(new_fr, new_to) = (points[i - 1] + 1, points[i])
					if new_fr != new_to:
						stack.append((new_fr, new_to, mn, h - 1))
				(new_fr, new_to) = (points[ix2 - 1] + 1, to)
				if new_fr != new_to:
					stack.append((new_fr, new_to, mn, h - 1))
	cache = get_cache(hh)
	sm = 0
	for (fr, to, h, delta) in gen(hh, cache, 0, len(hh), min(hh), max(hh)):
		sm += delta
		print('\tfr=%d to=%d h=%d delta=%d' % (fr, to, h, delta), file=sys.stderr)
	return sm

def solve(hh):
	print('hh=%s' % (hh,), file=sys.stderr)
	sm = 0
	stack = []
	for h in hh:
		if not stack:
			stack.append((h, 1))
		elif stack[-1][0] > h:
			stack.append((h, 1))
		elif stack[-1][0] == h:
			stack[-1] = (h, stack[-1][1] + 1)
		else:
			while stack and stack[-1][0] < h:
				(v, c) = stack.pop()
				sm += c * (c - 1)
			if not stack:
				stack.append((h, 1))
			elif stack[-1][0] > h:
				stack.append((h, 1))
			else:
				stack[-1] = (h, stack[-1][1] + 1)
	while stack:
		(v, c) = stack.pop()
		sm += c * (c - 1)
	return sm
tm = time()
_ = int(input())
hh = list(map(int, input().split()))
print(solve(hh))
print('time elapsed: %s' % (time() - tm,), file=sys.stderr)


import collections

def solve(nums):
	res = 0
	stack = []
	d = collections.Counter()
	for n in nums:
		res += d[n]
		while stack and stack[-1] < n:
			m = stack.pop()
			d[m] = 0
		stack.append(n)
		d[n] += 1
	return 2 * res
_ = int(input())
nums = list(map(int, input().split()))
print(solve(nums))


import os
import sys

def solve(l):
	st = []
	h = {}
	s = 0
	for i in l:
		while st and i > st[-1]:
			if st[-1] in h:
				del h[st[-1]]
			st.pop()
		if st and st[-1] == i:
			s += h[i]
		st.append(i)
		if i in h:
			h[i] += 1
		else:
			h[i] = 1
	return s * 2
ln = int(input())
l = list(map(int, input().split()))
print(solve(l))


n = int(input())
height = list(map(int, input().split()))
ans = 0
seen = []
times = {}
for i in height:
	if len(seen) == 0:
		seen.append(i)
		times[i] = 1
	elif seen[len(seen) - 1] == i:
		times[i] += 1
	elif seen[len(seen) - 1] > i:
		seen.append(i)
		if i in times:
			times[i] += 1
		else:
			times[i] = 1
	else:
		while len(seen) != 0 and seen[len(seen) - 1] < i:
			temp = seen.pop()
			ans += times[temp] * (times[temp] - 1)
			times[temp] = 0
		if len(seen) == 0:
			seen.append(i)
		elif seen[len(seen) - 1] != i:
			seen.append(i)
		if i in times:
			times[i] += 1
		else:
			times[i] = 1
while len(seen) != 0:
	temp = seen.pop()
	ans += times[temp] * (times[temp] - 1)
print(ans)