Alice is a kindergarten teacher. She wants to give some candies to the children in her class.  All the children sit in a line and each of them has a rating score according to his or her performance in the class.  Alice wants to give at least 1 candy to each child. If two children sit next to each other, then the one with the higher rating must get more candies. Alice wants to minimize the total number of candies she must buy.

Example  

$arr=[4,6,4,5,6,2]$    

She gives the students candy in the following minimal amounts: $[1,2,1,2,3,1]$.  She must buy a minimum of 10 candies.  

Function Description

Complete the candies function in the editor below.  

candies has the following parameter(s):  

int n: the number of children in the class  
int arr[n]: the ratings of each student  

Returns  

int: the minimum number of candies Alice must buy  

Input Format

The first line contains an integer, $n$, the size of $\textbf{arr}$. 

Each of the next $n$ lines contains an integer $arr\left[i\right]$ indicating the rating of the student at position $\boldsymbol{i}$.

Constraints

$1\leq n\leq10^5$  
$1\leq ar r[i]\leq10^5$ 

Sample Input 0
3
1
2
2

Sample Output 0
4

Explanation 0

Here 1, 2, 2 is the rating. Note that when two children have equal rating, they are allowed to have different number of candies. Hence optimal distribution will be 1, 2, 1.

Sample Input 1
10
2
4
2
6
1
7
8
9
2
1

Sample Output 1
19

Explanation 1

Optimal distribution will be $1,2,1,2,1,2,3,4,2,1$

Sample Input 2
8
2
4
3
5
2
6
4
5

Sample Output 2
12

Explanation 2

Optimal distribution will be $12121212$.

Difficulty: MEDIUM
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
N = int(input())
a = []
while N > 0:
	a.append(int(input()))
	N -= 1
N = len(a)
(left, right, num) = [[0 for i in range(N)] for j in range(3)]
p = 1
while p < N:
	if a[p] > a[p - 1]:
		left[p] = left[p - 1] + 1
	p += 1
p = N - 2
while p >= 0:
	if a[p] > a[p + 1]:
		right[p] = right[p + 1] + 1
	p -= 1
p = 0
while p < N:
	num[p] = 1 + max(left[p], right[p])
	p += 1
print(sum(num))


import sys
data = sys.stdin.readlines()

def min_count_of_candies(no_of_children, children_score):
	candies_given_to_children = [1 for index in range(no_of_children)]

	def neighbours_candie_count_if_my_score_less_than_neighours(my_index, neighbours_index):
		if children_score[my_index] > children_score[neighbours_index] and candies_given_to_children[my_index] <= candies_given_to_children[neighbours_index]:
			return candies_given_to_children[neighbours_index]
		return 0

	def give_candie_comparing_neighbours(child_index):
		candies_with_neighbours = [0]
		if child_index != 0:
			candies_with_neighbours.append(neighbours_candie_count_if_my_score_less_than_neighours(child_index, child_index - 1))
		if child_index != no_of_children - 1:
			candies_with_neighbours.append(neighbours_candie_count_if_my_score_less_than_neighours(child_index, child_index + 1))
		candies_given_to_children[child_index] = max(candies_with_neighbours) + 1

	def see_if_children_on_left_should_be_given_more_candies(child_index):
		for index in reversed(range(1, child_index + 1)):
			if children_score[index - 1] > children_score[index] and candies_given_to_children[index - 1] <= candies_given_to_children[index]:
				candies_given_to_children[index - 1] = candies_given_to_children[index] + 1
			else:
				break
	for index in range(no_of_children):
		no_of_candies_given_to_child = candies_given_to_children[index]
		give_candie_comparing_neighbours(index)
		if candies_given_to_children[index] != no_of_candies_given_to_child:
			see_if_children_on_left_should_be_given_more_candies(index)
	print(sum(candies_given_to_children))
(no_of_children, children_scores) = (int(data[0]), [int(score) for score in data[1:]])
min_count_of_candies(no_of_children, children_scores)


n = int(input())
r = [int(input()) for i in range(n)]
rt = [1]
for i in range(1, n):
	if r[i] > r[i - 1]:
		rt.append(rt[-1] + 1)
	elif r[i] < r[i - 1]:
		if rt[-1] != 1:
			rt.append(1)
		else:
			for j in range(i - 1, -1, -1):
				rt[j] += 1
				if r[j] >= r[j - 1] or rt[j - 1] > rt[j]:
					break
			rt.append(1)
	else:
		rt.append(1)
print(sum(rt))


import sys
N = int(sys.stdin.readline())
scores = [int(sys.stdin.readline()) for i in range(N)]
candies = [1] * N
for i in range(1, N):
	if scores[i] > scores[i - 1]:
		candies[i] = candies[i - 1] + 1
for i in range(N - 2, -1, -1):
	if scores[i] > scores[i + 1] and candies[i] <= candies[i + 1]:
		candies[i] = candies[i + 1] + 1
print(sum(candies))


import sys
N = int(sys.stdin.readline())
rating = [int(sys.stdin.readline()) for i in range(N)]
candies = [1] * N
for i in range(N - 1):
	if rating[i + 1] > rating[i]:
		candies[i + 1] = candies[i] + 1
for i in reversed(range(N - 1)):
	if rating[i] > rating[i + 1] and candies[i] <= candies[i + 1]:
		candies[i] = candies[i + 1] + 1
print(sum(candies))


kids = list()
for _ in range(int(input())):
	kids.append(int(input()))
candy = [0 for _ in kids]
for i in range(len(kids) - 1):
	if kids[i + 1] > kids[i] and candy[i + 1] <= candy[i]:
		candy[i + 1] = candy[i] + 1
for i in range(len(kids) - 1, 0, -1):
	if kids[i - 1] > kids[i] and candy[i - 1] <= candy[i]:
		candy[i - 1] = candy[i] + 1
count = len(kids)
for c in candy:
	count += c
print(count)


N = int(input())
ratings = []
candies = {}
for i in range(N):
	ratings.append(int(input()))
	if i == 0:
		candies[i] = 1
	elif ratings[i] > ratings[i - 1]:
		candies[i] = candies[i - 1] + 1
	elif ratings[i] == ratings[i - 1]:
		candies[i] = 1
	else:
		candies[i] = 1
		pos = i - 1
		while pos >= 0 and ratings[pos] > ratings[pos + 1] and (candies[pos] <= candies[pos + 1]):
			candies[pos] = candies[pos + 1] + 1
			pos -= 1
count = 0
for i in candies:
	count += candies[i]
print(count)


n = int(input())
freq = [int(input()) for _ in range(n)]
candie_r = [1] * len(freq)
candie_l = [1] * len(freq)
for i in range(1, len(candie_l)):
	if freq[i - 1] < freq[i]:
		candie_l[i] = candie_l[i - 1] + 1
for i in range(len(candie_r) - 2, -1, -1):
	if freq[i + 1] < freq[i]:
		candie_r[i] = candie_r[i + 1] + 1
print(sum(map(max, zip(candie_r, candie_l))))


def Solve():
	n = int(input())
	l = []
	for i in range(n):
		x = int(input())
		l.append(x)
	c = [1 for i in range(0, n)]
	for i in range(1, n):
		if l[i] > l[i - 1]:
			c[i] = c[i - 1] + 1
	c1 = [1 for i in range(0, n)]
	i = n - 2
	while i >= 0:
		if l[i] > l[i + 1]:
			c1[i] = c1[i + 1] + 1
		i -= 1
	ans = 0
	for i in range(n):
		if c[i] > c1[i]:
			ans += c[i]
		else:
			ans += c1[i]
	print(ans)
Solve()


N = int(input())
kids = []
for n in range(N):
	kids.append(int(input()))

def candy(ratings):
	count = 1
	candies = [1]
	for index in range(1, len(ratings)):
		if ratings[index] > ratings[index - 1]:
			count += 1
		else:
			count = 1
		candies.append(count)
	return candies
ll = candy(kids)
kids.reverse()
lr = candy(kids)
print(sum(map(max, zip(ll, reversed(lr)))))


N = int(input())
kids = []
for n in range(N):
	kids.append(int(input()))

def candy(ratings):
	count = 1
	candies = [1]
	for index in range(1, len(ratings)):
		if ratings[index] > ratings[index - 1]:
			count += 1
		else:
			count = 1
		candies.append(count)
	return candies
ll = candy(kids)
kids.reverse()
lr = candy(kids)
print(sum(map(max, zip(ll, reversed(lr)))))


N = int(input())
kids = []
for n in range(N):
	kids.append(int(input()))

def candy(ratings):
	count = 1
	candies = [1]
	for index in range(1, len(ratings)):
		if ratings[index] > ratings[index - 1]:
			count += 1
		else:
			count = 1
		candies.append(count)
	return candies
ll = candy(kids)
kids.reverse()
lr = candy(kids)
print(sum(map(max, zip(ll, reversed(lr)))))


N = int(input())
kids = []
for n in range(N):
	kids.append(int(input()))

def candy(ratings):
	count = 1
	candies = [1]
	for index in range(1, len(ratings)):
		if ratings[index] > ratings[index - 1]:
			count += 1
		else:
			count = 1
		candies.append(count)
	return candies
ll = candy(kids)
kids.reverse()
lr = candy(kids)
print(sum(map(max, zip(ll, reversed(lr)))))


c = 0
n = int(input())
h = 0
l = 0
r = []
s = []
for i in range(n):
	l = h
	h = int(input())
	if h > l:
		c += 1
	else:
		c = 1
	s.append(c)
	r.append(h)
	k = c
	m = 1
	if h < l:
		while m <= i and (s[i - m] == k and r[i - m] > r[i - m + 1]):
			s[i - m] += 1
			k = s[i - m]
			m += 1
print(sum(s))


forward_list = list()
backward_list = list()

def forward(rating):
	length = 0
	for i in range(1, len(rating)):
		if rating[i] > rating[i - 1]:
			length += 1
		else:
			length = 0
		forward_list[i] = length

def backward(rating):
	length = 0
	for i in range(len(rating) - 2, -1, -1):
		if rating[i] > rating[i + 1]:
			length += 1
		else:
			length = 0
		backward_list[i] = length

def downcount(i, rating):
	candy = 1
	candies = 0
	for j in range(i - 1, -1, -1):
		if rating[j] > rating[j + 1]:
			candy += 1
		else:
			candy = 1
		candy_map[j] = candy
		candies += candy
	return candies
answer = 0
l = int(input())
rating = list()
for i in range(l):
	rating.append(int(input()))
forward_list = [0] * len(rating)
backward_list = [0] * len(rating)
forward(rating)
backward(rating)
for i in range(len(rating)):
	answer += max(forward_list[i], backward_list[i]) + 1
print(answer)


import sys

def getInt():
	return int(sys.stdin.readline().strip())
N = getInt()
cost = 0
streak = streakDiff = None
prevRating = prevCandies = None
for i in range(N):
	crtRating = getInt()
	if i == 0:
		crtCandies = 1
		streak = 1
		streakDiff = 0
	elif crtRating < prevRating:
		crtCandies = 1
		if prevCandies == 1:
			cost += streak
			streak += 1
			if streakDiff:
				streakDiff -= 1
				if not streakDiff:
					cost += 1
					streak += 1
		else:
			streak = 1
			streakDiff = prevCandies - crtCandies
	elif crtRating == prevRating:
		crtCandies = 1
		streak = 1
		streakDiff = 0
	else:
		crtCandies = prevCandies + 1
		streak = 1
		streakDiff = 0
	cost += crtCandies
	prevRating = crtRating
	prevCandies = crtCandies
print(cost)


def minCandies(ratings):
	N = len(ratings)
	minR = [1 for x in range(N)]
	minL = [1 for x in range(N)]
	for i in range(N - 2, -1, -1):
		if ratings[i] > ratings[i + 1]:
			minR[i] = 1 + minR[i + 1]
	for i in range(1, N):
		if ratings[i] > ratings[i - 1]:
			minL[i] = 1 + minL[i - 1]
	result = 0
	for i in range(0, N):
		result = result + max(minL[i], minR[i])
	return result

def main():
	N = int(input())
	ratings = []
	while N > 0:
		ratings.append(int(input()))
		N = N - 1
	print(minCandies(ratings))
main()


def candies(children):
	minL = [1]
	for i in range(1, len(children)):
		if children[i] > children[i - 1]:
			minL.append(minL[i - 1] + 1)
		else:
			minL.append(1)
	(c, s) = (1, minL[len(children) - 1])
	for i in range(len(children) - 2, -1, -1):
		if children[i] > children[i + 1]:
			c += 1
		else:
			c = 1
		s += max(c, minL[i])
	return s
N = int(input())
children = [int(input()) for n in range(0, N)]
print(candies(children))


import sys
n = int(input())
scores = []
candies = []
for x in range(0, n):
	score = int(input())
	scores.append(score)
	candies.append(1)
	i = len(scores) - 2
	if i >= 0:
		if scores[i] < score:
			candies[-1] = candies[i] + 1
		elif scores[i] > score:
			j = i
			while j >= 0 and scores[j] > scores[j + 1] and (candies[j] <= candies[j + 1]):
				candies[j] += 1
				j -= 1
print(sum(candies))


import sys
n = int(sys.stdin.readline()) - 1
prev_rating = int(sys.stdin.readline())
prev_peak = 0
prev_candies = 1
fallstreak = 1
candies = 1
for i in range(n):
	rating = int(sys.stdin.readline())
	if rating > prev_rating:
		prev_candies = prev_candies + 1
		candies = candies + prev_candies
		fallstreak = 0
		prev_peak = prev_candies
	elif rating == prev_rating:
		prev_candies = 1
		candies = candies + prev_candies
		fallstreak = 1
		prev_peak = 0
	else:
		prev_candies = 1
		fallstreak = fallstreak + 1
		if fallstreak == prev_peak:
			fallstreak = fallstreak + 1
		candies = candies + fallstreak
	prev_rating = rating
sys.stdout.write('{}\n'.format(candies))


import sys
N = int(sys.stdin.readline())
rating = [int(sys.stdin.readline()) for i in range(N)]
candies = [1] * N
for i in range(N - 1):
	if rating[i + 1] > rating[i]:
		candies[i + 1] = candies[i] + 1
for i in reversed(range(N - 1)):
	if rating[i] > rating[i + 1] and candies[i] <= candies[i + 1]:
		candies[i] = candies[i + 1] + 1
print(sum(candies))


def rating(i, ratings):
	if i < 0 or i > len(ratings) - 1:
		return 100001
	return ratings[i]

def main():
	n = int(input())
	ratings = [int(input()) for _ in range(n)]
	valleys = [i for i in range(n) if rating(i + 1, ratings) >= rating(i, ratings) <= rating(i - 1, ratings)]
	candies = [0] * n
	for valley_i in valleys:
		candies[valley_i] = 1
		mountain_i = valley_i - 1
		while mountain_i >= 0 and ratings[mountain_i] > ratings[mountain_i + 1]:
			candies[mountain_i] = max(candies[mountain_i], candies[mountain_i + 1] + 1)
			mountain_i -= 1
		mountain_i = valley_i + 1
		while mountain_i <= n - 1 and ratings[mountain_i] > ratings[mountain_i - 1]:
			candies[mountain_i] = candies[mountain_i - 1] + 1
			mountain_i += 1
	print(sum(candies))
main()


N = int(input())
rating = [int(input())]
free = 0
drop = []
total = 1
previous = 1
for i in range(1, N):
	rating.append(int(input()))
	if rating[-1] > rating[-2]:
		previous += 1
		total += previous
		free = i
		drop = []
	elif rating[-1] == rating[-2]:
		previous = 1
		total += 1
		free = i
		drop = []
	else:
		if previous == 1:
			if len(drop) == 0:
				total += i - free
			else:
				total += i - drop.pop()
		else:
			for j in range(previous - 2):
				drop.append(i)
		previous = 1
		total += 1
print(total)


N = int(input())
grades = []
candies = [1] * N
for i in range(N):
	grades.append(int(input()))
for i in range(1, N):
	if grades[i - 1] < grades[i]:
		candies[i] = candies[i - 1] + 1
	else:
		j = i
		while j > 0 and grades[j - 1] > grades[j]:
			candies[j - 1] = max(candies[j - 1], candies[j] + 1)
			j -= 1
print(sum(candies))


import sys
N = int(sys.stdin.readline().strip())
ratings = []
while N > 0:
	ratings.append(int(sys.stdin.readline().strip()))
	N -= 1
cache = {}

def candy(left, middle, right):
	if (left, middle, right) in cache:
		return cache[left, middle, right]
	ratingmiddle = ratings[middle]
	if left < 0:
		ratingleft = 1000000.0
	else:
		ratingleft = ratings[left]
	if right >= len(ratings):
		ratingright = 1000000.0
	else:
		ratingright = ratings[right]
	if ratingmiddle > max(ratingleft, ratingright):
		cache[left, middle, right] = max(candy(left - 1, left, middle), candy(middle, right, right + 1)) + 1
	elif ratingmiddle > ratingleft and ratingmiddle <= ratingright:
		cache[left, middle, right] = candy(left - 1, left, middle) + 1
	elif ratingmiddle > ratingright and ratingmiddle <= ratingleft:
		cache[left, middle, right] = candy(middle, right, right + 1) + 1
	else:
		cache[left, middle, right] = 1
	return cache[left, middle, right]
print(sum((candy(i - 1, i, i + 1) for i in range(len(ratings)))))


a = []
for _ in range(int(input())):
	a.append(int(input()))
n = len(a)
c = [0] * n
c[0] = 1
for i in range(1, n):
	if a[i] > a[i - 1]:
		c[i] = c[i - 1] + 1
	else:
		c[i] = 1
		if c[i - 1] == 1 and a[i] < a[i - 1]:
			j = i - 1
			while j >= 0 and a[j] > a[j + 1] and (c[j] == c[j + 1]):
				c[j] += 1
				j -= 1
print(sum(c))


def min_candies(r):
	c = [1 for x in r]
	for j in range(1, len(r)):
		i = j - 1
		if r[i] < r[j]:
			c[j] = c[i] + 1
		else:
			c[j] = 1
			while i >= 0 and r[i] > r[i + 1] and (c[i] <= c[i + 1]):
				c[i] = c[i + 1] + 1
				i -= 1
	return sum(c)
N = int(input().strip())
rankings = [int(input().strip()) for i in range(N)]
print(min_candies(rankings))


import sys

def parse_input():
	rankings = []
	for line in sys.stdin:
		rankings.append(int(line))
	return rankings

def distribute_candies(rankings, n):
	opt = [0] * len(rankings)
	total_candies = 0
	for i in range(0, n):
		opt[i] = max_candy(rankings, i)
		total_candies += opt[i]
	return total_candies

def max_candy(rankings, i):
	max_candy_left = 1
	max_candy_right = 1
	for j in range(i - 1, -1, -1):
		if rankings[j] < rankings[i]:
			max_candy_left += 1
		else:
			break
		if j == 0 or rankings[j - 1] >= rankings[j]:
			break
	for k in range(i + 1, len(rankings)):
		if rankings[k] < rankings[i]:
			max_candy_right += 1
		else:
			break
		if k == len(rankings) - 1 or rankings[k + 1] >= rankings[k]:
			break
	return max(max_candy_left, max_candy_right)
n = int(sys.stdin.readline())
rankings = parse_input()
candies = distribute_candies(rankings, n)
print(candies)


def CandyCheck(index, score, bonbecs):
	if index > 0:
		if list[index - 1][0] < score:
			list[index][1] = list[index - 1][1] + 1
		else:
			index2 = index
			while index2 > 0 and list[index2 - 1][0] > list[index2][0]:
				list[index2 - 1][1] = max(list[index2 - 1][1], list[index2][1] + 1)
				index2 -= 1
tMax = int(input())
t = tMax
totalCandy = 0
list = [[0] * 2 for x in range(tMax)]
while t > 0:
	list[tMax - t][0] = int(input())
	list[tMax - t][1] = 1
	t -= 1
for (i, value) in enumerate(list):
	CandyCheck(i, *value)
for (i, value) in enumerate(list):
	totalCandy += value[1]
print(totalCandy)


n = int(input())
p = [0] + list(map(int, [input() for _ in range(n)])) + [0]
c = [0] + [1] * (len(p) - 2) + [0]
for i in range(1, n + 1):
	if p[i] > p[i - 1]:
		c[i] = c[i - 1] + 1
for i in range(n, 0, -1):
	if p[i] > p[i + 1]:
		c[i] = max(c[i], c[i + 1] + 1)
print(sum(c))


import sys
N = int(sys.stdin.readline())
rating = []
candies = []
for i in range(N):
	rating.append(int(sys.stdin.readline()))
	candies.append(1)
for i in range(N - 1):
	if rating[i] > rating[i + 1] and candies[i] <= candies[i + 1]:
		candies[i] = candies[i + 1] + 1
for i in range(1, N):
	if rating[i] > rating[i - 1] and candies[i] <= candies[i - 1]:
		candies[i] = candies[i - 1] + 1
for i in reversed(range(N - 1)):
	if rating[i] > rating[i + 1] and candies[i] <= candies[i + 1]:
		candies[i] = candies[i + 1] + 1
print(sum(candies))


def candy(N, L):
	can = 0
	dic1 = {0: 1}
	dic2 = {N - 1: 1}
	for i in range(1, N):
		if L[i - 1] < L[i]:
			dic1[i] = dic1[i - 1] + 1
		else:
			dic1[i] = 1
	for i in range(N - 2, -1, -1):
		if L[i + 1] < L[i]:
			dic2[i] = dic2[i + 1] + 1
		else:
			dic2[i] = 1
	for i in range(N):
		can += max(dic1[i], dic2[i])
	return can
N = int(input())
L = [int(input()) for i in range(N)]
print(candy(N, L))


def makeValues(values):
	last = values[0]
	output = []
	for i in range(len(values)):
		if values[i] == last:
			output.append(0)
		elif values[i] < last:
			if output[i - 1] > 0:
				output.append(-1)
			else:
				output.append(output[i - 1] - 1)
		elif values[i] > last:
			if output[i - 1] < 0:
				output.append(1)
			else:
				output.append(output[i - 1] + 1)
		last = values[i]
	return output

def minCandies(values):
	candies = 0
	if len(values) < 1:
		return candies
	ascendingValues = makeValues(values)
	values.reverse()
	descendingValues = makeValues(values)
	i = 0
	ii = len(values) - 1
	while i < len(values):
		if ascendingValues[i] <= 0 and descendingValues[ii] <= 0:
			candies += 1
		else:
			candies += max(ascendingValues[i], descendingValues[ii]) + 1
		i += 1
		ii -= 1
	return candies
students = int(input())
assert 1 <= students <= 100000
scores = []
for i in range(students):
	score = int(input())
	assert 1 <= score <= 100000
	scores.append(score)
print(minCandies(scores))


kids = int(input())
dp = [0] * kids
rates = [0] * kids
dp[0] = 1
rates[0] = int(input())
for i in range(1, kids):
	rates[i] = int(input())
	if rates[i] > rates[i - 1]:
		dp[i] = dp[i - 1] + 1
	else:
		dp[i] = 1
for i in range(1, kids):
	if rates[-1 - i] > rates[-i]:
		dp[-1 - i] = max(dp[-i] + 1, dp[-1 - i])
print(sum(dp))


ch = [int(input()) for i in range(int(input()))]
mms = []
(lmi, ma, nmi) = (0, -1, -1)
if ch[0] > ch[1]:
	lmi = ma = 0
for (i, c) in enumerate(ch[1:-1]):
	if ch[i] >= c <= ch[i + 2]:
		nmi = i + 1
		mms.append((lmi, ma, nmi))
		(lmi, ma, nmi) = (nmi, -1, -1)
	elif ch[i + 2] < c and ma == -1:
		ma = i + 1
	elif ch[i + 2] == c:
		if ma == -1:
			ma = i + 1
		nmi = i + 1
		mms.append((lmi, ma, nmi))
		(lmi, ma, nmi) = (nmi, -1, -1)
if ch[-1] <= ch[-2]:
	nmi = len(ch) - 1
	if ch[-1] == ch[-2]:
		ma = -1
	mms.append((lmi, ma, nmi))
else:
	mms.append((lmi, len(ch) - 1, len(ch) - 1))
s = 0
for (b, m, e) in mms:
	v = (m - b) * (m - b + 1) // 2 + (e - m) * (e - m + 1) // 2 + max(m - b, e - m) + 1
	if m == -1:
		v = 2
	s += v
print(s - len(mms) + 1)


import sys
T = int(sys.stdin.readline().strip())
A = list(map(lambda x: int(x.strip()), sys.stdin.readlines()))
B = [1] * len(A)
for i in range(1, len(A)):
	if A[i] > A[i - 1]:
		while B[i] <= B[i - 1]:
			B[i] = B[i] + 1
for i in range(len(A) - 2, -1, -1):
	if A[i] > A[i + 1]:
		while B[i] <= B[i + 1]:
			B[i] = B[i] + 1
print(sum(B))


n = int(input())
a = []
b = []
k = 0
for i in range(n):
	a.append(int(input()))
for i in range(n):
	b.append(1)
for j in range(50):
	k = k + 1
	for i in range(n):
		if i < n - 1:
			if a[i] > a[i + 1]:
				if b[i] <= b[i + 1]:
					b[i] = b[i] + 1
			elif a[i] < a[i + 1]:
				if b[i] >= b[i + 1]:
					b[i + 1] = b[i + 1] + 1
print(sum(b))


from collections import deque
N = int(input())
ratings = []
for i in range(N):
	ratings.append(int(input()))
f = deque([1])
r = deque([1])
for i in range(1, N):
	if ratings[i] > ratings[i - 1]:
		f.append(f[-1] + 1)
	else:
		f.append(1)
for i in reversed(range(N - 1)):
	if ratings[i] > ratings[i + 1]:
		r.appendleft(r[0] + 1)
	else:
		r.appendleft(1)
output = 0
for i in range(N):
	output += max(f[i], r[i])
print(output)


cases = int(input())
rating = []
for i in range(0, cases):
	rating.append(int(input()))
chocolates = [1] * len(rating)
for j in range(1, len(rating)):
	if rating[j] < rating[j - 1]:
		k = j - 1
		while k >= 0 and rating[k] > rating[k + 1]:
			if chocolates[k] <= chocolates[k + 1]:
				chocolates[k] += 1
			k = k - 1
	elif rating[j] > rating[j - 1]:
		chocolates[j] = chocolates[j - 1] + 1
res = 0
for choc in chocolates:
	res += choc
print(res)


import sys
N = int(sys.stdin.readline())
rating = [int(sys.stdin.readline()) for i in range(N)]
candies = [1] * N
for i in range(N - 1):
	if rating[i + 1] > rating[i]:
		candies[i + 1] = candies[i] + 1
for i in reversed(range(N - 1)):
	if rating[i] > rating[i + 1] and candies[i] <= candies[i + 1]:
		candies[i] = candies[i + 1] + 1
print(sum(candies))


def decreasingSequencesLengths(a):
	lods = [1] * len(a)
	for i in range(len(a) - 2, -1, -1):
		if a[i] > a[i + 1]:
			lods[i] = lods[i + 1] + 1
	return lods

def minCandies(a):
	(s, prev, prevcand) = (0, 0, 0)
	lods = decreasingSequencesLengths(a)
	for idx in range(len(a)):
		if a[idx] > prev:
			prevcand = max(prevcand + 1, lods[idx])
		else:
			prevcand = lods[idx]
		prev = a[idx]
		s += prevcand
	return s
n = int(input())
a = [0] * n
for i in range(n):
	a[i] = int(input())
print(minCandies(a))


N = int(input())
ratings = [int(input()) for i in range(N)]
candles = [0 for x in range(N)]
stack_f = [0 for x in range(N)]
stack_l = [0 for x in range(N)]
for i in range(1, N):
	if ratings[i] > ratings[i - 1]:
		if stack_f[i - 1] == 0:
			stack_f[i] = 2
		else:
			stack_f[i] = stack_f[i - 1] + 1
	if ratings[N - i - 1] > ratings[N - i]:
		if stack_l[N - i] == 0:
			stack_l[N - i - 1] = 2
		else:
			stack_l[N - i - 1] = stack_l[N - i] + 1
for i in range(N):
	candles[i] = max(stack_f[i], stack_l[i])
	if candles[i] == 0:
		candles[i] = 1
print(sum(candles))


memo = []

def walkRight(arr, start):
	if start == len(arr):
		return -1
	last = arr[start]
	for i in range(start + 1, len(arr)):
		if arr[i] >= last:
			return i
		last = arr[i]
	return len(arr)

def countem():
	return sum(memo)

def countCandies(arr):
	position = 0
	count = 0
	while position < len(arr):
		endPos = walkRight(arr, position)
		if endPos == -1:
			return countem()
		extra = 0
		if position > 0 and arr[position - 1] < arr[position]:
			extra = memo[position - 1]
		sm = endPos - position
		if sm <= extra:
			sm = extra + 1
		memo.append(sm)
		position += 1
	return countem()
students = int(input())
arr = []
for n in range(students):
	arr.append(int(input()))
print(countCandies(arr))


import sys

def solve(children):
	children_len = len(children)
	children_candies = [1 for child in children]
	pointer = 0
	while True:
		c_ch = children[pointer]
		c_ca = children_candies[pointer]
		if pointer == 0:
			p_ch = None
		else:
			p_ch = children[pointer - 1]
		try:
			n_ch = children[pointer + 1]
		except:
			n_ch = None
		if p_ch:
			p_ca = children_candies[pointer - 1]
			if c_ch > p_ch and c_ca <= p_ca:
				children_candies[pointer] += 1
				continue
			elif c_ch < p_ch and c_ca >= p_ca:
				pointer -= 1
				continue
		if n_ch:
			n_ca = children_candies[pointer + 1]
			if c_ch > n_ch and c_ca <= n_ca:
				children_candies[pointer] += 1
				continue
			else:
				pointer += 1
				continue
		else:
			return sum(children_candies)
		pointer += 1

def main():
	try:
		filename = sys.argv[1]
		data = open(filename, 'rb').readlines()
	except IndexError:
		data = sys.stdin.readlines()
	children = [int(v) for v in data[1:]]
	answer = solve(children)
	if answer:
		print(answer)
main()


t = int(input())
line = []
for i in range(0, t):
	a = input()
	line.append(int(a))

def count_candy(line):
	allocation = [1] * len(line)
	for index in range(1, len(line)):
		if line[index] > line[index - 1]:
			allocation[index] = allocation[index - 1] + 1
	for index in reversed(range(0, len(line) - 1)):
		if line[index] > line[index + 1]:
			allocation[index] = max(allocation[index + 1] + 1, allocation[index])
	return sum(allocation)
print(count_candy(line))


def get_minimum_candies(candy, ratings, k):
	if k == 0:
		return 0
	for i in range(1, k):
		c = candy[i]
		left = ratings[i - 1]
		mid = ratings[i]
		right = ratings[i + 1]
		if left < mid <= right:
			c = candy[i - 1] + 1
		elif left < mid and mid > right:
			c = candy[i - 1] + 1
		elif left > mid:
			j = i
			while i > 0 and ratings[j - 1] > ratings[j]:
				candy[j - 1] = max(candy[j - 1], candy[j] + 1)
				j -= 1
		elif left == mid or mid == right:
			c = 1
		candy[i] = c
	return candy
n = int(input())
ratings = []
candy = [1 for j in range(0, n + 1)]
for x in range(0, n):
	rating = int(input())
	ratings.append(rating)
ratings.append(0)
print(sum(get_minimum_candies(candy, ratings, n)) - 1)


def candies(ratings):
	candies = [1] * len(ratings)
	for i in range(1, len(ratings)):
		if ratings[i] > ratings[i - 1]:
			candies[i] = candies[i - 1] + 1
		if ratings[i] < ratings[i - 1]:
			if candies[i - 1] == 1:
				update(candies, ratings, i)
	return candies

def update(candies, ratings, i):
	for r in range(i):
		j = i - r - 1
		candies[j] += 1
		if ratings[j] == ratings[j - 1] or ratings[j] > ratings[j - 1]:
			break
		if ratings[j] < ratings[j - 1]:
			if candies[j] == candies[j - 1]:
				continue
			else:
				break
num_children = int(input())
ratings = [0] * num_children
for i in range(num_children):
	ratings[i] = int(input())
c = candies(ratings)
print(sum(c))


N = int(input())
children = [int(input()) for _ in range(N)]
candies = [0] * N

def candify(i):
	if candies[i] > 0:
		return candies[i]
	if i > 0 and children[i - 1] < children[i]:
		candies[i] = candify(i - 1) + 1
	if i < N - 1 and children[i + 1] < children[i]:
		candies[i] = max(candify(i + 1) + 1, candies[i])
	if candies[i] == 0:
		candies[i] = 1
	return candies[i]
for i in range(N):
	candify(i)
print(sum(candies))


import sys

def candies(ratings, num):
	candies_list = [1] * num
	sum_list = [1] * num
	dp = [0] * num
	for i in range(1, num):
		if ratings[i] > ratings[i - 1]:
			candies_list[i] = candies_list[i - 1] + 1
			sum_list[i] = sum_list[i - 1] + candies_list[i]
		elif ratings[i] < ratings[i - 1]:
			dp[i] = dp[i - 1] + 1
			if dp[i] < candies_list[i - dp[i]]:
				sum_list[i] = sum_list[i - 1] + dp[i]
			else:
				sum_list[i] = sum_list[i - 1] + dp[i] + 1
		else:
			sum_list[i] = sum_list[i - 1] + 1
	return sum_list[-1]
num_chil = int(sys.stdin.readline())
ratings = []
for chil in range(num_chil):
	ratings.append(int(sys.stdin.readline()))
print(candies(ratings, num_chil))


N = int(input())
arr = []
for i in range(N):
	arr.append(int(input()))
val = [0] * N
val[0] = 1
total = 1
for i in range(N - 1):
	if arr[i + 1] < arr[i]:
		val[i + 1] = 1
		total = total + 1
	elif arr[i + 1] == arr[i]:
		val[i + 1] = 1
		total = total + 1
	elif arr[i + 1] > arr[i]:
		val[i + 1] = val[i] + 1
		total = total + val[i] + 1
for i in reversed(range(1, N)):
	if arr[i - 1] > arr[i] and val[i - 1] <= val[i]:
		val[i - 1] = val[i] + 1
		total = total - val[i - 1] + val[i] + 1
total = 0
for x in val:
	total = total + x
print(total)


N = int(input())
cs = [int(input()) for i in range(N)]
candies = [1] * N
if N == 1:
	print(1)
else:
	for i in range(1, N):
		if cs[i] > cs[i - 1]:
			candies[i] = candies[i - 1] + 1
	for i in range(N - 2, -1, -1):
		if cs[i] > cs[i + 1] and candies[i] <= candies[i + 1]:
			candies[i] = candies[i + 1] + 1
	print(sum(candies))


n = int(input())
array = [1 for i in range(n)]
userinput = [1 for i in range(n)]
for i in range(n):
	userinput[i] = int(input())
for i in range(1, n):
	if userinput[i] > userinput[i - 1]:
		array[i] = array[i - 1] + 1
total = array[n - 1]
for i in range(n - 2, -1, -1):
	if userinput[i] > userinput[i + 1]:
		array[i] = max(array[i], array[i + 1] + 1)
	total += array[i]
print(total)


t = int(input())
a = [None] * t
b = [0] * t
c = [0] * t
for i in range(t):
	a[i] = int(input())
for i in range(1, t):
	if a[i] > a[i - 1]:
		b[i] = b[i - 1] + 1
for i in range(t - 2, -1, -1):
	if a[i] > a[i + 1]:
		c[i] = c[i + 1] + 1
s = 0
for i in range(t):
	s += max(c[i], b[i])
print(s + t)


N = int(input())
a = []
while N > 0:
	a.append(int(input()))
	N -= 1
N = len(a)
(left, right, num) = [[0 for i in range(N)] for j in range(3)]
p = 1
while p < N:
	if a[p] > a[p - 1]:
		left[p] = left[p - 1] + 1
	p += 1
p = N - 2
while p >= 0:
	if a[p] > a[p + 1]:
		right[p] = right[p + 1] + 1
	p -= 1
p = 0
while p < N:
	num[p] = 1 + max(left[p], right[p])
	p += 1
print(sum(num))


import sys
N = int(sys.stdin.readline())
rating = [int(sys.stdin.readline()) for i in range(N)]
candies = [1] * N
for i in range(N - 1):
	if rating[i + 1] > rating[i]:
		candies[i + 1] = candies[i] + 1
for i in reversed(range(N - 1)):
	if rating[i] > rating[i + 1] and candies[i] <= candies[i + 1]:
		candies[i] = candies[i + 1] + 1
print(sum(candies))


number_count = int(input())
numbers = []
number_to_indexes = dict()
for i in range(0, number_count):
	current_number = int(input())
	if current_number in number_to_indexes:
		number_to_indexes[current_number].append(len(numbers))
	else:
		number_to_indexes[current_number] = [len(numbers)]
	numbers.append(current_number)
candy_count = [0] * len(numbers)
sorted_keys = sorted(number_to_indexes.keys())
for current_number in sorted_keys:
	for current_index in number_to_indexes[current_number]:
		prev_value = candy_count[current_index - 1] if current_index > 0 else 0
		next_value = candy_count[current_index + 1] if current_index < len(candy_count) - 1 else 0
		prev_number = numbers[current_index - 1] if current_index > 0 else 0
		next_number = numbers[current_index + 1] if current_index < len(numbers) - 1 else 0
		if numbers[current_index] <= prev_number:
			prev_value = 0
		if numbers[current_index] <= next_number:
			next_value = 0
		candy_count[current_index] = max(prev_value, next_value) + 1
print(sum(candy_count))


def candies(ratings):
	N = len(ratings)
	dp = [1] * N
	for i in range(1, N):
		if ratings[i] > ratings[i - 1]:
			dp[i] = dp[i - 1] + 1
		elif ratings[i] == ratings[i - 1]:
			dp[i] = 1
		else:
			dp[i] = min(1, dp[i - 1] - 1)
		if dp[i] < 1:
			j = i - 1
			dp[i] = 1
			while j >= 0 and (ratings[j] > ratings[j + 1] and dp[j] <= dp[j + 1]):
				dp[j] += 1
				j -= 1
	return sum(dp)
childs = int(input())
ratings = []
for i in range(childs):
	ratings.append(int(input()))
print(candies(ratings))


N = int(input())
lst = []
for i in range(N):
	num = int(input())
	lst.append(num)
lst1 = [1]
for i in range(1, N):
	if lst[i] > lst[i - 1]:
		lst1.append(lst1[i - 1] + 1)
	else:
		lst1.append(1)
lst2 = [1]
for i in range(1, N):
	if lst[N - i - 1] > lst[N - i]:
		lst2.append(lst2[i - 1] + 1)
	else:
		lst2.append(1)
for i in range(N):
	lst[i] = max(lst1[i], lst2[N - i - 1])
print(str(sum(lst)))


import sys
children = [int(line) for line in sys.stdin.readlines()][1:]
candy = [0 for i in range(len(children))]
order = sorted([(children[i], i) for i in range(len(children))])
for (val, idx) in order:
	m = 0
	if idx > 0 and children[idx - 1] < val and (candy[idx - 1] > m):
		m = candy[idx - 1]
	if idx < len(children) - 1 and children[idx + 1] < val and (candy[idx + 1] > m):
		m = candy[idx + 1]
	candy[idx] = m + 1
print(sum(candy))


n = int(input())
rate = []
for i in range(n):
	rate.append(int(input()))
candies = [1] * n
updated = True
while updated:
	updated = False
	for i in range(n - 1):
		if rate[i] > rate[i + 1] and candies[i] <= candies[i + 1]:
			updated = True
			candies[i] = candies[i + 1] + 1
		elif rate[i] < rate[i + 1] and candies[i] >= candies[i + 1]:
			updated = True
			candies[i + 1] = candies[i] + 1
print(sum(candies))


def nond(a, i):
	x = 1
	while a[i - 1] > a[i]:
		x += 1
		i -= 1
	return x
t = int(input())
ar = []
for _ in range(t):
	ar.append(int(input()))
lefts = [1] * t
rights = [1] * t
for i in range(1, t):
	if ar[i] > ar[i - 1]:
		lefts[i] = 1 + lefts[i - 1]
for i in range(t - 2, -1, -1):
	if ar[i] > ar[i + 1]:
		rights[i] = 1 + rights[i + 1]
s = 0
for i in range(t):
	s += max(lefts[i], rights[i])
print(s)


import os, sys, itertools
N = int(input())

def dfs(src, mask, res, pos):
	mask[pos] = True
	ans = 1
	if pos > 0 and src[pos - 1] < src[pos]:
		ans = max(ans, dfs(src, mask, res, pos - 1) + 1)
	if pos < N - 1 and src[pos + 1] < src[pos]:
		ans = max(ans, dfs(src, mask, res, pos + 1) + 1)
	res[pos] = ans
	return ans
src = [None] * N
mask = [False] * N
res = [None] * N
for i in range(N):
	src[i] = int(input())
for i in range(N):
	if not mask[i]:
		dfs(src, mask, res, i)
print(sum(res))


import sys
N = int(sys.stdin.readline())
rating = [int(sys.stdin.readline()) for i in range(N)]
candies = [1] * N
for i in range(N - 1):
	if rating[i + 1] > rating[i]:
		candies[i + 1] = candies[i] + 1
for i in reversed(range(N - 1)):
	if rating[i] > rating[i + 1] and candies[i] <= candies[i + 1]:
		candies[i] = candies[i + 1] + 1
print(sum(candies))


def min_candies(ratings):
	candies = [1] * len(ratings)
	for i in range(1, len(ratings)):
		if ratings[i] > ratings[i - 1]:
			candies[i] = candies[i - 1] + 1
	for i in range(len(ratings) - 2, -1, -1):
		if ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]:
			candies[i] = candies[i + 1] + 1
	return sum(candies)
n = int(input())
ratings = [int(input()) for _ in range(n)]
print(min_candies(ratings))


array = [int(input()) for _ in range(int(input()))]
rating = [[idx, array[idx]] for idx in range(len(array))]
rating.sort(key=lambda a: a[1])
candies = [0 for _ in range(len(array))]
last_rate = 0
for rate in rating:
	idx = rate[0]
	candies[idx] = 1
	if idx > 0 and array[idx - 1] < array[idx]:
		candies[idx] = candies[idx - 1] + 1
	if idx < len(array) - 1 and array[idx] > array[idx + 1]:
		candies[idx] = max(candies[idx], candies[idx + 1] + 1)
print(sum(candies))


def cal(a, n):
	ar = [1]
	for i in range(1, n):
		if a[i] > a[i - 1]:
			ar.append(ar[i - 1] + 1)
		else:
			ar.append(1)
	for i in range(2, n + 1):
		if a[-i] > a[-i + 1] and ar[-i] <= ar[-i + 1]:
			ar[-i] = ar[-i + 1] + 1
	s = 0
	for k in ar:
		s = s + k
	return s
n = int(input())
a = []
for i in range(n):
	a.append(int(input()))
print(cal(a, n))


children = []
candies = []
num = int(input())
for i in range(num):
	children.append(int(input()))
	candies.append(0)
if children[0] > children[1]:
	candies[0] = 2
	candies[1] = 1
elif children[0] < children[1]:
	candies[0] = 1
	candies[1] = 2
else:
	candies[0] = 1
	candies[1] = 1
for i in range(2, num):
	if children[i] > children[i - 1]:
		candies[i] = candies[i - 1] + 1
	elif children[i] <= children[i - 1]:
		candies[i] = 1
for i in reversed(range(1, num - 1)):
	if children[i] > children[i + 1]:
		if candies[i] <= candies[i + 1]:
			candies[i] = candies[i + 1] + 1
print(sum(candies))


def set_increasing_scores(rating):
	updated = False
	for i in range(1, len(rating)):
		if rating[i][0] > rating[i - 1][0] and rating[i][1] <= rating[i - 1][1]:
			rating[i] = (rating[i][0], rating[i - 1][1] + 1)
			updated = True
	return updated
n = int(input())
rating = []
for _ in range(n):
	rating.append((int(input()), 1))
while set_increasing_scores(rating) == True:
	rating.reverse()
print(sum((v[1] for v in rating)))


T = int(input())
rating = []
for _ in range(T):
	rating.append(int(input()))
left = [1 for _ in range(T)]
right = [1 for _ in range(T)]
for i in range(1, T):
	if rating[i] > rating[i - 1]:
		left[i] = left[i - 1] + 1
for i in range(T - 1)[::-1]:
	if rating[i] > rating[i + 1]:
		right[i] = right[i + 1] + 1
print(sum([max(left[i], right[i]) for i in range(T)]))


num = int(input())
students = []
candies = []
for _ in range(num):
	students.append(int(input()))
	candies.append(1)
for _ in range(num - 1):
	if students[_] < students[_ + 1]:
		candies[_ + 1] = candies[_] + 1
	if students[_] > students[_ + 1] and candies[_] <= candies[_ + 1]:
		candies[_] = candies[_ + 1] + 1
for x in range(num - 1):
	_ = num - x - 1
	if students[_] < students[_ - 1]:
		candies[_ - 1] = candies[_] + 1
	if students[_] > students[_ - 1] and candies[_] <= candies[_ - 1]:
		candies[_] = candies[_ - 1] + 1
print(sum(candies))


def candycount(rating):
	(better, worse) = [[[] for _ in range(len(rating))] for __ in 'ab']
	candy = [None] * len(rating)
	for (i, (lf, rt)) in enumerate(zip(rating, rating[1:])):
		if lf < rt:
			better[i].append(i + 1)
			worse[i + 1].append(i)
		elif lf > rt:
			better[i + 1].append(i)
			worse[i].append(i + 1)
	worsecount = list(map(len, worse))
	pending = [i for (i, w) in enumerate(worsecount) if w == 0]
	while pending:
		i = pending.pop()
		candy[i] = 1 + max((candy[j] for j in worse[i])) if worse[i] else 1
		for j in better[i]:
			worsecount[j] -= 1
			if worsecount[j] == 0:
				pending.append(j)
	assert not any((c is None for c in candy))
	return sum(candy)
nstudents = int(input())
students = []
for _ in range(nstudents):
	students.append(int(input()))
print(candycount(students))


def main():
	import sys
	N = int(input())
	ratings = []
	candies = []
	for x in sys.stdin:
		ratings.append(int(x))
		candies.append(1)
	for i in range(N - 1):
		if ratings[i] < ratings[i + 1]:
			candies[i + 1] = candies[i] + 1
	for i in range(N - 2, -1, -1):
		if ratings[i] > ratings[i + 1]:
			candies[i] = max(candies[i], candies[i + 1] + 1)
	print(sum(candies))
main()


N = int(input())
r = list((int(input()) for _ in range(N)))
(ml, mr) = ([1] * N, [1] * N)
for i in range(1, N):
	if r[i - 1] < r[i]:
		ml[i] = ml[i - 1] + 1
	j = N - 1 - i
	if r[j + 1] < r[j]:
		mr[j] = mr[j + 1] + 1
print(sum((max(x, y) for (x, y) in zip(ml, mr))))


def get1():
	return int(input())

def solve(t, r):
	c = [1] * t
	for i in range(1, t):
		if r[i] > r[i - 1]:
			c[i] = c[i - 1] + 1
	for i in range(t - 1, 0, -1):
		if r[i - 1] > r[i] and c[i - 1] <= c[i]:
			c[i - 1] = c[i] + 1
	return sum(c)

def main():
	t = get1()
	r = []
	for i in range(t):
		c = get1()
		r.append(c)
	print(solve(t, r))
main()


N = int(input())
mas = list()
for i in range(N):
	mas.append(int(input()))
result = [1] * N
if mas[0] > mas[1]:
	result[0] += 1
if mas[len(mas) - 1] > mas[len(mas) - 2]:
	result[len(mas) - 1] += 1
for i in range(1, len(result) - 1):
	if mas[i] <= mas[i - 1]:
		if mas[i] > mas[i + 1]:
			result[i] += 1
	else:
		result[i] = result[i - 1] + 1
bol = True
while bol:
	gol = False
	for i in range(len(result) - 2):
		if result[i] == result[i + 1]:
			if mas[i] > mas[i + 1]:
				result[i] += 1
				gol = True
			elif mas[i] < mas[i + 1]:
				result[i + 1] += 1
				gol = True
	if gol == False:
		bol = False
candies = 0
for i in result:
	candies += i
print(candies)


n = int(input())
a = [int(input()) for _ in range(n)]
candies = [1] * n
for i in range(1, n):
	if a[i] > a[i - 1]:
		candies[i] = candies[i - 1] + 1
for i in range(n - 2, -1, -1):
	if a[i] > a[i + 1]:
		candies[i] = max(candies[i], candies[i + 1] + 1)
print(sum(candies))


n = int(input())
a = [0] * n
for _ in range(n):
	a[_] = int(input())
c = [1] * n
for i in range(1, n):
	if a[i] > a[i - 1]:
		c[i] = c[i - 1] + 1
for i in range(n - 2, -1, -1):
	if a[i] > a[i + 1]:
		c[i] = max(c[i], c[i + 1] + 1)
print(sum(c))


n = int(input())
a = [int(input()) for _ in range(n)]
candies = [1] * n
for i in range(1, n):
	if a[i] > a[i - 1]:
		candies[i] = candies[i - 1] + 1
for i in range(n - 2, -1, -1):
	if a[i] > a[i + 1]:
		candies[i] = max(candies[i], candies[i + 1] + 1)
print(sum(candies))


def solve(scores):
	l = len(scores)
	candies = [1] * l
	(pos, d, dry) = (1, 1, True)
	while True:
		if scores[pos - d] < scores[pos] and candies[pos - d] >= candies[pos]:
			candies[pos] = candies[pos - d] + 1
			dry = False
		pos += d
		if pos in (-1, l):
			if not dry:
				pos = 1 if -1 == d else l - 2
				(d, dry) = (-d, True)
			else:
				break
	return sum(candies)
n = int(input().strip())
print(solve([int(input().strip()) for _ in range(n)]))


n = int(input())
li = []
for _ in range(n):
	li.append(int(input()))
fromLeft = [1] * n
fromRight = [1] * n
for i in range(1, n):
	if li[i] > li[i - 1]:
		fromLeft[i] = fromLeft[i - 1] + 1
for i in range(n - 2, -1, -1):
	if li[i] > li[i + 1]:
		fromRight[i] = fromRight[i + 1] + 1
ans = 0
for i in range(n):
	ans += max(fromLeft[i], fromRight[i])
print(ans)


n = int(input())
a = []
for i in range(n):
	num = int(input())
	a.append(num)
candies = [1] * n
for i in range(1, n):
	if a[i] > a[i - 1]:
		candies[i] = candies[i - 1] + 1
for i in range(n - 2, -1, -1):
	if a[i] > a[i + 1]:
		candies[i] = max(candies[i], candies[i + 1] + 1)
print(sum(candies))


N = int(input())
kids = list()
for i in range(N):
	kids.append(int(input()))
result = [1] * N
for dir in range(2):
	for i in range(1, N):
		if kids[i] > kids[i - 1]:
			temp = result[i - 1] + 1
			result[i] = max(result[i], temp)
	kids.reverse()
	result.reverse()
print(str(sum(result)))


import sys
N = int(sys.stdin.readline())
rating = [int(sys.stdin.readline()) for i in range(N)]
candies = [1] * N
for i in range(N - 1):
	if rating[i + 1] > rating[i]:
		candies[i + 1] = candies[i] + 1
for i in reversed(range(N - 1)):
	if rating[i] > rating[i + 1] and candies[i] <= candies[i + 1]:
		candies[i] = candies[i + 1] + 1
print(sum(candies))


n = int(input())
l = []
k = []
for i in range(n):
	l.append(int(input()))
	k.append(0)
k[0] = 1
for i in range(1, n):
	if l[i] > l[i - 1]:
		k[i] = k[i - 1] + 1
	if l[i] < l[i - 1]:
		k[i] = 1
		j = i
		while l[j] < l[j - 1] and k[j] == k[j - 1]:
			k[j - 1] += 1
			j -= 1
	if l[i] == l[i - 1]:
		k[i] = 1
print(sum(k))


import sys
N = int(sys.stdin.readline())
rating = [int(sys.stdin.readline()) for i in range(N)]
candies = [1] * N
for i in range(N - 1):
	if rating[i + 1] > rating[i]:
		candies[i + 1] = candies[i] + 1
for i in reversed(range(N - 1)):
	if rating[i] > rating[i + 1] and candies[i] <= candies[i + 1]:
		candies[i] = candies[i + 1] + 1
print(sum(candies))


def backtrack(starting_index, candies, ratings):
	while candies[starting_index - 1] <= candies[starting_index] and ratings[starting_index - 1] > ratings[starting_index]:
		candies[starting_index - 1] = candies[starting_index] + 1
		starting_index -= 1
N = int(input())
ratings = list()
candies = [1] * N
for i in range(N):
	ratings.append(int(input()))
for i in range(0, len(ratings)):
	if i + 1 <= len(ratings) - 1 and ratings[i] < ratings[i + 1]:
		candies[i + 1] = candies[i] + 1
	elif i + 1 <= len(ratings) - 1 and ratings[i] >= ratings[i + 1]:
		candies[i + 1] = 1
	if i > 0 and ratings[i - 1] > ratings[i] and (candies[i - 1] <= candies[i]):
		backtrack(i, candies, ratings)
print(sum(candies))


N = int(input())
ratings = [int(input()) for _ in range(N)]
candies = [1] * N
for i in range(N - 1):
	if ratings[i + 1] > ratings[i]:
		candies[i + 1] = candies[i] + 1
for i in range(N - 1, 0, -1):
	if ratings[i - 1] > ratings[i]:
		candies[i - 1] = max(candies[i - 1], candies[i] + 1)
print(sum(candies))


total = int(input())
students = [int(input()) for _ in range(total)]
candies = [1] * total
for i in range(1, total):
	if students[i] > students[i - 1]:
		candies[i] = candies[i - 1] + 1
for i in range(total - 2, -1, -1):
	if students[i] > students[i + 1]:
		candies[i] = max(candies[i + 1] + 1, candies[i])
print(sum(candies))


def solution(c):
	if len(c) == 1:
		return 1
	candy = [1 for i in range(len(c))]
	for i in range(1, len(c)):
		if c[i] > c[i - 1]:
			candy[i] = candy[i - 1] + 1
	for i in range(len(c) - 2, -1, -1):
		if c[i] > c[i + 1]:
			candy[i] = max(candy[i], candy[i + 1] + 1)
	return sum(candy)
numOfChildren = int(input())
c = []
for i in range(numOfChildren):
	c.append(int(input()))
print(solution(c))


import sys
N = int(sys.stdin.readline())
rating = [int(sys.stdin.readline()) for i in range(N)]
candies = [1] * N
for i in range(N - 1):
	if rating[i + 1] > rating[i]:
		candies[i + 1] = candies[i] + 1
for i in reversed(range(N - 1)):
	if rating[i] > rating[i + 1] and candies[i] <= candies[i + 1]:
		candies[i] = candies[i + 1] + 1
print(sum(candies))


num = int(input())
L = []
for i in range(num):
	k = int(input())
	L.append(k)
start = 0
dp = [0] * len(L)
dp[0] = 1
for i in range(1, len(L)):
	if L[i] > L[i - 1]:
		start = i
		dp[i] = dp[i - 1] + 1
	elif L[i] == L[i - 1]:
		start = i
		dp[i] = 1
	else:
		dp[i] = 1
		for j in range(i - 1, start - 1, -1):
			if dp[j] == dp[j + 1]:
				dp[j] += 1
print(sum(dp))


import sys
N = int(sys.stdin.readline())
rating = [int(sys.stdin.readline()) for i in range(N)]
candies = [1] * N
for i in range(N - 1):
	if rating[i + 1] > rating[i]:
		candies[i + 1] = candies[i] + 1
for i in reversed(range(N - 1)):
	if rating[i] > rating[i + 1] and candies[i] <= candies[i + 1]:
		candies[i] = candies[i + 1] + 1
print(sum(candies))


n = int(input())
a = [int(input()) for _ in range(n)]
candies = [1] * n
for i in range(1, n):
	if a[i] > a[i - 1]:
		candies[i] = candies[i - 1] + 1
for i in range(n - 2, -1, -1):
	if a[i] > a[i + 1]:
		candies[i] = max(candies[i], candies[i + 1] + 1)
print(sum(candies))


n = int(input())
lis = []
for _ in range(n):
	x = int(input())
	lis.append(x)
L = [1 for _ in range(n)]
R = L[:]
for i in range(1, n):
	if lis[i - 1] < lis[i]:
		L[i] = L[i - 1] + 1
for i in range(n - 2, -1, -1):
	if lis[i + 1] < lis[i]:
		R[i] = R[i + 1] + 1
res = 0
for x in zip(L, R):
	res += max(x)
print(res)


n = int(input())
a = [1] * n
for i in range(n):
	a[i] = int(input())
candies = [1] * n
for i in range(1, n):
	if a[i] > a[i - 1]:
		candies[i] = candies[i - 1] + 1
ans = 0
i = n - 2
while i >= 0:
	if a[i] > a[i + 1]:
		candies[i] = max(candies[i], candies[i + 1] + 1)
	ans = ans + candies[i]
	i = i - 1
print(str(ans + candies[n - 1]))


def candies(list_input):
	if len(list_input) == 1:
		return 1
	left_right = [1] * len(list_input)
	for i in range(1, len(list_input)):
		if list_input[i] > list_input[i - 1]:
			left_right[i] = left_right[i - 1] + 1
		else:
			left_right[i] = 1
	for i in range(-2, -len(list_input) - 1, -1):
		if list_input[i] > list_input[i + 1]:
			left_right[i] = max(left_right[i], left_right[i + 1] + 1)
	return sum(left_right)
list_input = []
for _ in range(int(input())):
	list_input.append(int(input()))
res = candies(list_input)
print(res)


n = int(input())
a = [int(input()) for _ in range(n)]
c = [1] * n
for i in range(1, n):
	if a[i] > a[i - 1]:
		c[i] = c[i - 1] + 1
for i in range(n - 2, -1, -1):
	if a[i] > a[i + 1]:
		c[i] = max(c[i], c[i + 1] + 1)
print(sum(c))


import sys
N = int(sys.stdin.readline())
rating = [int(sys.stdin.readline()) for i in range(N)]
candies = [1] * N
for i in range(N - 1):
	if rating[i + 1] > rating[i]:
		candies[i + 1] = candies[i] + 1
for i in reversed(range(N - 1)):
	if rating[i] > rating[i + 1] and candies[i] <= candies[i + 1]:
		candies[i] = candies[i + 1] + 1
print(sum(candies))