Shik loves sorted intervals. But currently he does not have enough time to sort all the numbers. So he decided to use Almost sorted intervals. An Almost sorted interval is a consecutive subsequence in a sequence which satisfies the following property:

The first number is the smallest.
The last number is the largest.

Please help him count the number of almost sorted intervals in this permutation.  

Note: Two intervals are different if at least one of the starting or ending indices are different.

Input Format 

The first line contains an integer N. 

The second line contains a permutation from 1 to N.

Output Format 

Output the number of almost sorted intervals.  

Constraints 

1 ≤ N ≤ $10^{6}  $

Sample Input  

5
3 1 2 5 4

Sample Output  

8

Explanation 

The subsequences [3], [1], [1 2], [1 2 5], [2], [2 5], [5], [4] are almost sorted intervals.

Source: hackerrank | Difficulty: HARD
Tags: Data structures


Solutions:
import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


from collections import namedtuple
N = None
LST = None
DATA_IN_SRC = False
READ_FROM_FILE = False
if DATA_IN_SRC:
	N = 5
	LST = (3, 1, 2, 5, 4)
elif READ_FROM_FILE:
	with open('input08.txt') as f:
		N = int(f.readline())
		LST = tuple((int(e) for e in f.readline().split()))
else:
	N = int(input())
	LST = tuple((int(e) for e in input().split()))

def count_almost_sorted_simple(lst):
	size = len(lst)
	count = 0
	for i in range(size):
		m = smax = lst[i]
		for j in range(i, size):
			n = lst[j]
			if n < m:
				break
			if n >= smax:
				smax = n
				count += 1
	return count

def count_almost_sorted(lst):
	size = len(lst)
	if size <= 2:
		if size <= 1:
			return size
		if lst[0] > lst[1]:
			return 2
		else:
			return 3
	if is_sorted(lst):
		return size * (size + 1) // 2
	if size < 30:
		return count_almost_sorted_simple(lst)
	mid = size // 2
	left = lst[:mid]
	right = lst[mid:]
	return count_join_almost_sorted_opt(left, right) + count_almost_sorted(left) + count_almost_sorted(right)

def is_sorted(lst):
	for idx in range(len(lst) - 1):
		if lst[idx] > lst[idx + 1]:
			return False
	return True
ElementInfo = namedtuple('ElementInfo', ['value', 'min', 'max'])

def count_join_almost_sorted(left, right):
	lmax = lmin = left[-1]
	left_infos = []
	for e in reversed(left):
		if e < lmin:
			lmin = e
		if e > lmax:
			lmax = e
		if lmin == e:
			left_infos.append(ElementInfo(e, lmin, lmax))
	rmax = rmin = right[0]
	right_infos = []
	for e in right:
		if e < rmin:
			rmin = e
		if e > rmax:
			rmax = e
		if e == rmax:
			right_infos.append(ElementInfo(e, rmin, rmax))
	count = 0
	rlen = len(right_infos)
	min_limit = 0
	max_limit = 0
	for linfo in left_infos:
		while min_limit < rlen and right_infos[min_limit].min >= linfo.min:
			min_limit += 1
		while max_limit < rlen and right_infos[max_limit].max < linfo.max:
			max_limit += 1
		if max_limit >= rlen:
			break
		if min_limit > max_limit:
			count += min_limit - max_limit
	return count

def count_join_almost_sorted_opt(left, right):
	lmax = lmin = left[-1]
	left_infos = []
	for e in reversed(left):
		if e <= lmin:
			lmin = e
			left_infos.append((lmin, lmax))
		elif e > lmax:
			lmax = e
	rmax = rmin = right[0]
	right_infos = []
	for e in right:
		if e < rmin:
			rmin = e
		elif e >= rmax:
			rmax = e
			right_infos.append((rmin, rmax))
	count = 0
	rlen = len(right_infos)
	min_limit = 0
	max_limit = 0
	for linfo in left_infos:
		while min_limit < rlen and right_infos[min_limit][0] >= linfo[0]:
			min_limit += 1
		while max_limit < rlen and right_infos[max_limit][1] < linfo[1]:
			max_limit += 1
		if max_limit >= rlen:
			break
		if min_limit > max_limit:
			count += min_limit - max_limit
	return count

def inner_loop(left_infos, right_infos):
	count = 0
	rlen = len(right_infos)
	min_limit = 0
	max_limit = 0
	for linfo in left_infos:
		while min_limit < rlen and right_infos[min_limit][1] >= linfo[1]:
			min_limit += 1
		while max_limit < rlen and right_infos[max_limit][2] < linfo[2]:
			max_limit += 1
		if max_limit >= rlen:
			break
		if min_limit > max_limit:
			count += min_limit - max_limit
	return count
print(count_almost_sorted(LST))


N = int(input())
sequence = list(map(int, input().split()))
minima = []
max_counts = []
maxima = []

def countIntervals():
	num_intervals = 0
	for entry in sequence:
		while minima and minima[-1] > entry:
			remove_min()
		minima.append(entry)
		entry_max_tally = 1
		while maxima and maxima[-1] < entry:
			entry_max_tally += max_counts.pop()
			maxima.pop()
		maxima.append(entry)
		max_counts.append(entry_max_tally)
		num_intervals += entry_max_tally
	return num_intervals

def remove_min():
	minima.pop()
	max_counts[-1] -= 1
	if not max_counts[-1]:
		maxima.pop()
		max_counts.pop()
print(countIntervals())


from bisect import *

def main():
	length = int(input())
	perm = list(map(int, input().split()))
	assert len(perm) == length
	count = 0
	(ismall, ibig) = ([], [])
	for (iend, end) in enumerate(perm):
		while ismall and perm[ismall[-1]] > end:
			ismall.pop()
		while ibig and perm[ibig[-1]] < end:
			ibig.pop()
		ismall.append(iend)
		ibig.append(iend)
		if len(ibig) == 1:
			count += len(ismall)
		else:
			x = bisect(ismall, ibig[-2])
			count += len(ismall) - x
	print(count)
main()


def Sol(a):
	res = 0
	N = len(a)
	stack1_value = [a[-1]]
	stack1_index = [N - 1]
	stack2 = []
	for i in range(N - 2, -1, -1):
		value = a[i]
		if value < stack1_value[-1]:
			while stack2 and value < stack2[-1][0]:
				stack2.pop()
			if not stack2:
				res += len(stack1_value)
			else:
				index = stack2[-1][1]
				lo = 0
				hi = len(stack1_index) - 1
				while lo < hi:
					mid = (lo + hi) // 2
					if index < stack1_index[mid]:
						lo = mid + 1
					else:
						hi = mid
				res += len(stack1_index) - lo
		else:
			while stack1_value and value > stack1_value[-1]:
				last_value = stack1_value.pop()
				last_index = stack1_index.pop()
				while stack2 and last_value < stack2[-1][0]:
					stack2.pop()
				stack2.append((last_value, last_index))
		stack1_value.append(value)
		stack1_index.append(i)
	return res
N = int(input())
a = list(map(int, input().split()))
res = Sol(a)
res += N
print(res)


from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import *
from sys import exit, stderr

def read(f):
	return map(f, input().split())

def readlist(f):
	return [f(x) for x in input().split()]
(N,) = read(int)
A = readlist(int)

def nearestSmallerValues(iterable, default=None):
	stack = []
	for value in iterable:
		while stack and stack[-1] >= value:
			stack.pop()
		yield (stack[-1] if stack else default)
		stack.append(value)

def fenwick_lsb(index):
	return index & -index

def fenwick_init(list):
	size = len(list)
	for index in range(size):
		succ = index + fenwick_lsb(index + 1)
		if succ < size:
			list[succ] += list[index]

def fenwick_add(list, index, value):
	size = len(list)
	while index < size:
		list[index] += value
		index += fenwick_lsb(index + 1)

def fenwick_get(list, index):
	value = list[index]
	last = index + 1 - fenwick_lsb(index + 1)
	while index > last:
		value -= list[index - 1]
		index -= fenwick_lsb(index)
	return value

def fenwick_set(list, index, value):
	curr = fenwick_get(list, index)
	if curr != value:
		fenwick_add(list, index, value - curr)

def fenwick_sum(list, first, last, start=0):
	result = start
	while first < last:
		result += list[last - 1]
		last -= fenwick_lsb(last)
	while first > last:
		result -= list[first - 1]
		first -= fenwick_lsb(first)
	return result
peaks = [-1 if p is None else p[1] for p in nearestSmallerValues(((-A[k], k) for k in range(N)))]
troughs = [N if p is None else p[1] for p in nearestSmallerValues(((A[k], k) for k in reversed(range(N))))]
troughs.reverse()
print(A[:100], file=stderr)
print(peaks[:100], file=stderr)
print(troughs[:100], file=stderr)
ans = 0
removeStarts = []
validStarts = [1] * N
fenwick_init(validStarts)
for i in range(N):
	while removeStarts and removeStarts[0][0] <= i:
		j = heappop(removeStarts)[1]
		fenwick_set(validStarts, j, 0)
	n = fenwick_sum(validStarts, peaks[i] + 1, i + 1)
	ans += n
	right = troughs[i]
	if right >= 0:
		heappush(removeStarts, (right, i))
print(ans)


from bisect import bisect
from collections import deque
length = int(input())
a = list(map(int, input().split()))
ans = 0
(small, large) = ([] for i in range(2))
for (end, last) in enumerate(a):
	while large and a[large[len(large) - 1]] < last:
		large.pop()
	while small and a[small[-1]] > last:
		small.pop()
	small.append(end)
	large.append(end)
	if len(large) != 1:
		x = bisect(small, large[-2])
		ans += len(small) - x
	else:
		ans += len(small)
print(ans)


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


from bisect import bisect
n = int(input())
a = [n + 1, *map(int, input().split())]
ans = 0
inc = []
dec = [0]
for i in range(1, n + 1):
	while a[dec[-1]] < a[i]:
		dec.pop()
	x = dec[-1]
	dec.append(i)
	k = bisect(inc, x)
	ans += 1 + len(inc) - k
	while inc and a[inc[-1]] > a[i]:
		inc.pop()
	inc.append(i)
print(ans)


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import math
import os
import random
import re
import sys
import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for (i, ai) in enumerate(ais):
	if ai < cur_height:
		merged = True
		while merged:
			if not intervals or intervals[-1][-1] > cur_interval[-1]:
				intervals.append(cur_interval)
				break
			pi = intervals.pop()
			mpi_top = bisect.bisect_right(pi, cur_interval[0])
			pi[mpi_top:] = cur_interval
			cur_interval = pi
		cur_interval = []
	cur_height = ai
	cur_interval.append(ai)
	total_sequences += len(cur_interval)
	prev_min = cur_interval[0]
	for prev_interval_i in range(len(intervals) - 1, -1, -1):
		pi = intervals[prev_interval_i]
		if pi[-1] > ai:
			break
		pi_lower = bisect.bisect_right(pi, prev_min)
		if pi_lower > 0:
			prev_min = pi[0]
		total_sequences += pi_lower
print(total_sequences)


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))


import sys

def permute(l):
	l = l[:1] + l[:]
	n = len(l)
	nn = n + 12
	left = [0] * n
	right = [n] * n
	stack = left[:]
	arr = [0] * nn
	r = [[] for _ in range(n)]
	top = 0
	for i in range(1, n):
		val = l[i]
		while top > 0 and val > l[stack[top - 1]]:
			top -= 1
		if top:
			left[i] = stack[top - 1]
		stack[top] = i
		top += 1
	top = 0
	for i in range(n - 1, 0, -1):
		val = l[i]
		while top > 0 and val < l[stack[top - 1]]:
			top -= 1
		if top:
			right[i] = stack[top - 1]
		stack[top] = i
		top += 1
	ans = 0
	for i in range(n - 1, 0, -1):
		for j in r[i]:
			while j <= nn:
				arr[j] += -1
				j += j & -j
		j = i
		while j <= nn:
			arr[j] += 1
			j += j & -j
		r[left[i]].append(i)
		v = 0
		x = right[i] - 1
		while x > 0:
			v += arr[x]
			x -= x & -x
		ans += v
	return ans
n = sys.stdin.readline().split()
l = tuple(map(int, sys.stdin.readline().split()))
print(permute(l))