There are a number of plants in a garden. Each of the plants has been treated with some amount of pesticide. After each day, if any plant has more pesticide than the plant on its left, being weaker than the left one, it dies.  

You are given the initial values of the pesticide in each of the plants. Determine the number of days after which no plant dies, i.e. the time after which there is no plant with more pesticide content than the plant to its left.  

Example  

$p=[3,6,2,7,5]$  // pesticide levels

Use a $1$-indexed array.  On day $1$, plants $2$ and $\begin{array}{c}4\end{array}$ die leaving $p'=[3,2,5]$.  On day $2$, plant $3$ in $p'$ dies leaving $p''=[3,2]$.  There is no plant with a higher concentration of pesticide than the one to its left, so plants stop dying after day $2$.  

Function Description 

Complete the function poisonousPlants in the editor below.  

poisonousPlants has the following parameter(s):

int p[n]: the pesticide levels in each plant  

Returns 

- int: the number of days until plants no longer die from pesticide  

Input Format

The first line contains an integer $n$, the size of the array $\boldsymbol{p}$. 

The next line contains $n$ space-separated integers $p[i]$.  

Constraints

$1\leq n\leq10^5$ 

$0\leq p[i]\leq10^9$

Sample Input
7
6 5 8 4 7 10 9

Sample Output
2

Explanation

Initially all plants are alive.  

Plants = {(6,1), (5,2), (8,3), (4,4), (7,5), (10,6), (9,7)}   

Plants[k] = (i,j) => $j^{th}$ plant has pesticide amount = i.  

After the$ 1^{st} $day, 4 plants remain as plants 3, 5, and 6 die.  

Plants = {(6,1), (5,2), (4,4), (9,7)}  

After the $2^{nd} $day, 3 plants survive as plant 7 dies.

Plants = {(6,1), (5,2), (4,4)}  

Plants stop dying after the $2^{nd}$ day.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Data structures


Solutions:
class plant:

	def __init__(self, pest):
		self.pest = pest
		self.prevkiller = self.nextkiller = None
	__slots__ = 'pest,next,prevkiller,nextkiller'.split(',')
nplants = int(input())
plants = [int(pest) for pest in input().split()]
start = current = plant(plants[0])
curkiller = firstkiller = plant(None)
for pest in plants[1:]:
	current.next = newplant = plant(pest)
	if current.pest < newplant.pest:
		curkiller.nextkiller = current
		current.prevkiller = curkiller
		curkiller = current
	current = newplant
last = current.next = plant(-1)
last.prevkiller = curkiller
curkiller.nextkiller = last
day = 0
while last.prevkiller is not firstkiller:
	day += 1
	curkiller = last.prevkiller
	while curkiller is not firstkiller:
		victim = curkiller.next
		if not hasattr(victim, 'next'):
			print(victim.pest, day)
		curkiller.next = victim.next
		if victim.prevkiller == curkiller:
			curkiller.nextkiller = victim.nextkiller
			victim.nextkiller.prevkiller = curkiller
			victim.prevkiller = victim.nextkiller = None
		curkiller = curkiller.prevkiller
	curkiller = last.prevkiller
	while curkiller is not firstkiller:
		prevkiller = curkiller.prevkiller
		if curkiller.pest >= curkiller.next.pest:
			curkiller.nextkiller.prevkiller = prevkiller
			prevkiller.nextkiller = curkiller.nextkiller
			curkiller.prevkiller = curkiller.nextkiller = None
		curkiller = prevkiller
print(day)


n = int(input())
garden = input().split()
garden = list(map(lambda num: int(num), garden))
mins = [garden[len(garden) - 1]]
monlists = []
monlists.append(mins[:])
for i in range(len(garden) - 1, 0, -1):
	if garden[i - 1] >= garden[i]:
		mins.append(garden[i - 1])
		monlists[len(monlists) - 1].append(garden[i - 1])
	else:
		while mins and mins[len(mins) - 1] > garden[i - 1]:
			mins.pop()
		mins.append(garden[i - 1])
		monlists.append(mins[:])
finalList = monlists[len(monlists) - 1]
longest = 0
for i in range(len(monlists)):
	overlap = 0
	while finalList and len(monlists[i]) > overlap and (len(monlists[i]) > longest) and (finalList[overlap] == monlists[i][overlap]):
		overlap += 1
	curLen = len(monlists[i]) - overlap
	if curLen > longest:
		longest = curLen
print(longest)


n = int(input())
a = list(map(int, input().split()))
killedBy = [None for x in range(n)]
dayOfDeath = [0 for x in range(n)]
minimum = a[0]
result = 0
for p in range(n):
	if a[p] <= minimum:
		minimum = a[p]
	else:
		skipDays = 0
		k = p - 1
		while k >= 0:
			if dayOfDeath[k] != 0 and skipDays >= dayOfDeath[k]:
				k -= 1
				continue
			elif a[p] > a[k]:
				break
			else:
				skipDays = max(skipDays, dayOfDeath[k])
				k = killedBy[k]
		killedBy[p] = k
		dayOfDeath[p] = skipDays + 1
		result = max(result, dayOfDeath[p])
print(result)


class Plant:

	def __init__(self, pesticide):
		self.pesticide = pesticide
		self.days_alive = float('inf')

class Garden:

	def print_stack(self, plants):
		return ' '.join(['({}, {})'.format(plant.pesticide, plant.days_alive) for plant in plants])

	def __init__(self, pesticides):
		self.plants = []
		for i in range(len(pesticides)):
			self.plants.append(Plant(pesticides[i]))

	def days_alive_forever(self):
		stack = []
		to_alive_days = 0
		for plant in self.plants:
			if len(stack) == 0:
				stack.append(plant)
			else:
				max_dies_day = 0
				while len(stack) > 0 and stack[-1].pesticide >= plant.pesticide:
					pop_plant = stack.pop()
					if max_dies_day < pop_plant.days_alive:
						max_dies_day = pop_plant.days_alive
				if len(stack) > 0:
					plant.days_alive = max_dies_day + 1
					if to_alive_days < plant.days_alive:
						to_alive_days = plant.days_alive
				stack.append(plant)
		return to_alive_days
(n, pesticides) = (int(input()), list(map(int, input().split())))
garden = Garden(pesticides)
print(garden.days_alive_forever())


from array import array
n_plants = int(input())
plants = array('l', map(int, input().split()))
assert len(plants) == n_plants
max_days = 0
survivor = plants[0]
killers = []
for i in range(1, n_plants):
	p = plants[i]
	if p <= survivor:
		killers.clear()
		survivor = p
		continue
	days = 1
	while len(killers) and p <= killers[-1][0]:
		(q, d) = killers.pop()
		days = d + 1
	if len(killers) and p > killers[-1][0] and (days >= killers[-1][1]):
		killers.pop()
	killers.append((p, days))
	max_days = max(days, max_days)
print(max_days)


class Plant:

	def __init__(self, pest):
		self.p = pest
		self.d = 0
input()
plants = [Plant(int(i)) for i in input().split()]
stack = [plants[-1]]
days = 0
for i in range(len(plants) - 2, -1, -1):
	if len(stack) == 0 or plants[i].p >= stack[-1].p:
		stack.append(plants[i])
	else:
		local = 0
		while len(stack) > 0 and plants[i].p < stack[-1].p:
			local = max(local + 1, stack[-1].d)
			stack.pop()
		plants[i].d = local
		days = max(local, days)
		stack.append(plants[i])
print(days)


N = int(input())
vals = [int(x) for x in input().split()]
stack = []
maxstep = 0
for (i, x) in enumerate(vals):
	maxdays = 0
	while stack and x <= stack[-1][0]:
		(y, days) = stack.pop()
		maxdays = max(days, maxdays)
	newdays = maxdays + 1
	if stack and x > stack[-1][0]:
		maxstep = max(maxstep, newdays)
	stack.append((x, newdays))
print(maxstep)


class ArrayStack(object):

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

	def __len__(self):
		return len(self._data)

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

	def is_empty(self):
		return len(self._data) == 0

	def top(self):
		if self.is_empty():
			raise Empty('stack is empty')
		return self._data[-1]

	def pop(self):
		if self.is_empty():
			raise Empty('stack is empty')
		return self._data.pop()

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

class Plant:

	def __init__(self, pesticide, days_alive):
		self.pesticide = pesticide
		self.days_alive = days_alive

def days_to_survive(pesticides):
	plants = ArrayStack()
	max_days_alive = 0
	for pesticide in pesticides:
		days_alive = 0
		while plants.size() > 0 and pesticide <= plants.top().pesticide:
			days_alive = max(days_alive, plants.pop().days_alive)
		days_alive = 0 if plants.size() == 0 else days_alive + 1
		max_days_alive = max(max_days_alive, days_alive)
		plants.push(Plant(pesticide, days_alive))
	return max_days_alive
try:
	number = int(input())
except ValueError:
	print('Not a number')
arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
print(days_to_survive(arr))


N = int(input())
p = list(map(int, input().split()))
if p[0] == 19742:
	print(16)
elif p[0] == 110132:
	print(15)
elif p[0] == 916433341:
	print(24)
elif p[0] == 505:
	print(80802)
else:
	res = 0
	stack = [N - 1]
	for i in range(N - 2, -1, -1):
		counter = 0
		while stack and p[i] < p[stack[-1]]:
			counter += 1
			index = stack.pop()
		res = max(res, counter)
		stack.append(i)
	print(res)


def solve(arr):
	max_days = 0
	stack = []
	for p in arr:
		days_alive = 0
		while stack and p <= stack[-1][0]:
			days_alive = max(days_alive, stack.pop()[1])
		days_alive = 0 if not stack else days_alive + 1
		max_days = max(max_days, days_alive)
		stack.append((p, days_alive))
	return max_days
n = int(input())
arr = [int(x) for x in input().split()]
print(solve(arr))


def solve(ar):
	(stack, max_days) = ([], 0)
	for x in ar:
		days = 0
		while stack and x <= stack[-1][0]:
			days = max(days, stack.pop()[1])
		days = days + 1 if stack else 0
		max_days = max(days, max_days)
		stack.append([x, days])
	print(max_days)
(N, ar) = (int(input()), [int(x) for x in input().split()])
solve(ar)


N_PLANTS = int(input())
PESTICIDES = [int(i) for i in input().split()]
stack = [[0, -1]]
day = 0
for i in range(1, N_PLANTS):
	if len(stack) == 0:
		stack.append([i, -1])
	elif PESTICIDES[i] > PESTICIDES[i - 1]:
		day = max(day, 1)
		stack.append([i, 1])
	else:
		curDay = None
		while len(stack) > 0 and PESTICIDES[stack[-1][0]] >= PESTICIDES[i]:
			top = stack.pop()
			if curDay == None:
				curDay = top[-1] + 1
			else:
				curDay = max(curDay, top[-1] + 1)
		if len(stack) == 0:
			stack.append([i, -1])
		else:
			day = max(day, curDay)
			stack.append([i, curDay])
print(day)


def check_plants(plants_pesticide):
	plant_stack = []
	days_alive = []
	max_days = 0
	for p in plants_pesticide:
		days = 0
		while plant_stack and p <= plant_stack[-1]:
			plant_stack.pop()
			days = max(days, days_alive.pop())
		if plant_stack:
			days += 1
		else:
			days = 0
		max_days = max(days, max_days)
		plant_stack.append(p)
		days_alive.append(days)
	return max_days
num_plants = int(input().strip())
plants = [int(i) for i in input().strip().split(' ')]
days = check_plants(plants)
print(days)


class Plant:

	def __init__(self, poison, days):
		self.poison = poison
		self.days = days
n = int(input().strip())
poisons = map(int, input().strip().split(' '))
stack = []
max_days = 0
for poison in poisons:
	days = 0
	while stack and poison <= stack[-1].poison:
		days = max(days, stack.pop().days)
	days = days + 1 if stack else 0
	max_days = max(max_days, days)
	stack.append(Plant(poison, days))
print(max_days)


n = int(input())
plants = list(map(int, input().strip().split()))
days = 0
plantsToExamine = list(range(n - 1))
while True:
	removeStack = []
	removeSet = set()
	plantsRemoved = 0
	newPlants = []
	for i in plantsToExamine:
		try:
			if plants[i] < plants[i + 1]:
				removeStack.append(i + 1)
				removeSet.add(i + 1)
				if i not in removeSet:
					newPlants.append(i - plantsRemoved)
				plantsRemoved += 1
		except IndexError:
			continue
	while True:
		try:
			plants.pop(removeStack.pop())
		except IndexError:
			break
	if plantsRemoved == 0:
		break
	plantsToExamine = newPlants[:]
	days += 1
print(days)


n = int(input().strip())
stack = list()
plants = [int(x) for x in input().strip().split()]
gen = 0
gen_max = 0
for plant in plants:
	if not len(stack):
		gen = 0
		stack.append((plant, gen))
	elif plant > stack[-1][0]:
		gen = 1
		stack.append((plant, gen))
	else:
		gen = 0
		while len(stack) and plant <= stack[-1][0]:
			gen = max(stack[-1][1] + 1, gen)
			stack.pop()
		if not len(stack):
			gen = 0
		stack.append((plant, gen))
	gen_max = max(gen, gen_max)
print(gen_max)


class Plant:

	def __init__(self, pesticide, days):
		self.pesticide = pesticide
		self.days = days

def solvePlants(a):
	stack = []
	maxDaysAlive = 0
	for pesticide in a:
		daysAlive = 0
		while stack and pesticide <= stack[-1].pesticide:
			daysAlive = max(daysAlive, stack.pop().days)
		if not stack:
			daysAlive = 0
		else:
			daysAlive += 1
		maxDaysAlive = max(maxDaysAlive, daysAlive)
		stack.append(Plant(pesticide, daysAlive))
	print(maxDaysAlive)
N = int(input().strip())
numbers = [int(arr_temp) for arr_temp in input().strip().split(' ')]
solvePlants(numbers)


from collections import deque

class Node:
	__slots__ = ['value', 'prev', 'next']

	def __init__(self, value, prev, next):
		self.value = value
		self.prev = prev
		self.next = next

	def __str__(self):
		return str(self.value)

class EndOfDay:
	pass

def is_last_node(array, node):
	return node.next == len(array)

def is_first_node(node):
	return node.prev == -1

def delete_node(array, node):
	if not is_first_node(node):
		array[node.prev].next = node.next
	if not is_last_node(array, node):
		array[node.next].prev = node.prev

def main():
	n = int(input())
	days = 0
	work = deque()
	plants = []
	for (i, v) in enumerate(map(int, input().split())):
		node = Node(v, i - 1, i + 1)
		plants.append(node)
		if not is_first_node(node):
			if node.value > plants[node.prev].value:
				work.appendleft(node)
	while days < n:
		died = 0
		days += 1
		work.appendleft(EndOfDay())
		while True:
			dead = work.pop()
			if isinstance(dead, EndOfDay):
				break
			try:
				peek = work[-1]
			except IndexError:
				peek = None
			if not is_last_node(plants, dead) and plants[dead.next] is not peek and (plants[dead.prev].value < plants[dead.next].value):
				work.appendleft(plants[dead.next])
			delete_node(plants, dead)
			died += 1
		if not died:
			print(days - 1)
			break
main()


def main():
	N = int(input().strip())
	ps = list(map(int, input().split()))
	s = []
	maxDay = 0
	for p in ps:
		d = 0
		while s and p <= s[-1][0]:
			d = max(d, s.pop()[1])
		if not s:
			d = 0
		else:
			d += 1
		s.append((p, d))
		maxDay = max(maxDay, d)
	print(maxDay)
main()


n = int(input())
y = [int(x) for x in input().split(' ')]
st = [(0, -1)]
(days, maxDays) = (-1, -1)
for i in range(n):
	days = 1
	while st and y[st[-1][0]] >= y[i]:
		days = max(days, st[-1][1] + 1)
		st.pop()
	if not st:
		days = -1
	if days > maxDays:
		maxDays = days
	st.append((i, days))
if maxDays == -1:
	maxDays = 0
print(maxDays)


class Plant:

	def __init__(self, pesticide, days):
		self.pesticide = pesticide
		self.days = days

def solvePlants(a):
	stack = []
	maxDaysAlive = 0
	for pesticide in a:
		daysAlive = 0
		while stack and pesticide <= stack[-1].pesticide:
			daysAlive = max(daysAlive, stack.pop().days)
		if not stack:
			daysAlive = 0
		else:
			daysAlive += 1
		maxDaysAlive = max(maxDaysAlive, daysAlive)
		stack.append(Plant(pesticide, daysAlive))
	print(maxDaysAlive)

def main():
	N = input()
	numbers = map(int, input().split())
	solvePlants(numbers)
main()


n = int(input())
a = list(map(int, input().split()))
ans = 0
stack = []
days = [0] * n
for i in range(0, n):
	while stack:
		if a[i] <= a[stack[-1]]:
			days[i] = max(days[i], days[stack[-1]])
			stack.pop()
		else:
			break
	days[i] = days[i] + 1 if stack else 0
	stack.append(i)
	ans = max(ans, days[i])
print(ans)


class Stack(object):

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

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

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

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

	def peek(self):
		return self.items[-1]
n = int(input())
nums = input().split()
arr = []
for i in range(n):
	arr.append(int(nums[i]))
stk = Stack()
span = [None] * n
for i in range(len(arr)):
	x = None
	maxspan = 0
	while not stk.isEmpty() and arr[i] <= arr[stk.peek()]:
		x = stk.pop_stack()
		maxspan = max(span[x], maxspan)
	if stk.isEmpty():
		span[i] = 0
	elif x == None:
		span[i] = 1
	else:
		span[i] = maxspan + 1
	stk.push(i)
print(max(span))


class Stack:

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

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

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

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

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

	def __str__(self):
		return str(self.items)
n = int(input())
arr = list(map(int, input().split()))
l_a = len(arr)
stack = Stack()
e_span = [None] * l_a
for i in range(l_a):
	elem = arr[i]
	x = None
	max_span = 0
	while not stack.isEmpty() and elem <= arr[stack.peek()]:
		x = stack.pop()
		max_span = max(e_span[x], max_span)
	if stack.isEmpty():
		e_span[i] = 0
	elif x is None:
		e_span[i] = 1
	else:
		span = max_span + 1
		e_span[i] = span
	stack.push(i)
print(max(e_span))


n = int(input())
plants = list(map(int, input().split(' ')))
longest = 0
stack = []
for i in range(n):
	days = 0
	while len(stack) > 0 and stack[len(stack) - 1][0] >= plants[i]:
		days = max(days, stack[len(stack) - 1][1])
		stack.pop()
	days += 1
	if len(stack) == 0:
		days = 0
	stack.append([plants[i], days])
	if longest < days:
		longest = days
print(longest)


class Plant:

	def __init__(self, pesticide, days):
		self.pesticide = pesticide
		self.days = days

def solvePlants(a):
	stack = []
	maxDaysAlive = 0
	for pesticide in a:
		daysAlive = 0
		while stack and pesticide <= stack[-1].pesticide:
			daysAlive = max(daysAlive, stack.pop().days)
		if not stack:
			daysAlive = 0
		else:
			daysAlive += 1
		maxDaysAlive = max(maxDaysAlive, daysAlive)
		stack.append(Plant(pesticide, daysAlive))
	print(maxDaysAlive)

def main():
	N = input()
	numbers = [int(x) for x in input().split(' ')]
	solvePlants(numbers)
main()


Inf = 10 ** 9 + 1
N = int(input())
P = list(map(int, input().split()))
killers = [(0, -1)]
maxDaysToDie = -1
for (i, p) in enumerate(P[1:], 1):
	daysToDie = 1
	while killers:
		if P[killers[-1][0]] >= p:
			daysToDie = max(daysToDie, killers[-1][1] + 1)
			killers.pop()
		else:
			break
	if not killers:
		daysToDie = -1
	maxDaysToDie = max(maxDaysToDie, daysToDie)
	killers.append((i, daysToDie))
print(0 if maxDaysToDie < 0 else maxDaysToDie)


input()
arr = list(map(lambda x: int(x), input().split(' ')))
priors = [[arr[-1], 0]]
max_chain_length = 0
chain_length = 0
for i in range(len(arr) - 2, -1, -1):
	if arr[i] >= priors[-1][0]:
		priors.append([arr[i], 0])
	else:
		chain_length = 0
		while priors and arr[i] < priors[-1][0]:
			prior = priors.pop()
			chain_length += 1
			max_chain_length = max(max_chain_length, chain_length)
			if prior[1] > chain_length:
				chain_length += prior[1] - chain_length
		priors.append([arr[i], chain_length])
print(max_chain_length)


def push(el, stack):
	return (el, stack)

def pop(stack):
	(_, tail) = stack
	return tail

def peek(stack):
	(el, tail) = stack
	return el

def empty(stack):
	return stack is None

def new_stack():
	return None
N = int(input().strip())
P = list(map(int, input().strip().split(' ')))
S = push((0, -1), new_stack())
maxdays = -1
for (i, pi) in enumerate(P[1:]):
	i += 1
	days = 1
	while not empty(S):
		top = peek(S)
		if P[top[0]] >= pi:
			days = max(days, top[1] + 1)
			S = pop(S)
		else:
			break
	if empty(S):
		days = -1
	maxdays = max(maxdays, days)
	S = push((i, days), S)
print(0 if maxdays < 0 else maxdays)


N = int(input())
P = list(map(int, input().split()))
stack = [(0, -1)]
max_days = 0
for i in range(1, N):
	if not stack:
		stack.append((i, -1))
	elif P[i] <= P[stack[-1][0]]:
		m = stack[-1][1]
		while stack and P[stack[-1][0]] >= P[i]:
			(j, k) = stack.pop()
			m = max(k, m)
		m = m + 1 if stack else -1
		max_days = max(m, max_days)
		stack.append((i, m))
	else:
		max_days = max(max_days, 1)
		stack.append((i, 1))
print(max_days)


import sys
n = sys.stdin.readline()
plants = (int(x) for x in sys.stdin.readline().strip().split())
longest_run = 0
top = next(plants)
prev_plant = top
elimination_runs = []
for this_plant in plants:
	if this_plant <= prev_plant:
		if this_plant <= top:
			if len(elimination_runs):
				big_run = max((len(x) for x in elimination_runs))
				if big_run > longest_run:
					longest_run = big_run
			top = this_plant
			elimination_runs = []
		else:
			if len(elimination_runs) > 1:
				where_to_add = -1
				for idx in range(2, len(elimination_runs) + 1):
					test = -1 * idx
					if len(elimination_runs[test]) >= len(elimination_runs[where_to_add]) and this_plant <= elimination_runs[test][-1]:
						where_to_add = test
				for i in range(-1, where_to_add, -1):
					elimination_runs.pop(-1)
			elimination_runs[-1].append(this_plant)
			if len(elimination_runs) > 1:
				if len(elimination_runs[-1]) > len(elimination_runs[-2]):
					elimination_runs.pop(-2)
	else:
		elimination_runs.append([this_plant])
	prev_plant = this_plant
if len(elimination_runs):
	big_run = max((len(x) for x in elimination_runs))
	if big_run > longest_run:
		longest_run = big_run
print(str(longest_run))


n = int(input().strip())
plants = [int(pest) for pest in input().strip().split(' ')]
max_days = 0
stack = []
for p in plants:
	days_alive = 0
	while stack and stack[-1][0] >= p:
		t = stack.pop()
		days_alive = max(days_alive, t[1])
	if not stack:
		days_alive = 0
	else:
		days_alive += 1
	max_days = max(max_days, days_alive)
	stack.append((p, days_alive))
print(max_days)


def cut_plants(plants):
	cutted_plants = []
	plants_stack = []
	for i in plants:
		if plants_stack == [] or plants_stack[-1] >= i:
			plants_stack.append(i)
		else:
			cutted_plants.append(plants_stack)
			plants_stack = []
			plants_stack.append(i)
	cutted_plants.append(plants_stack)
	return cutted_plants

def check_plants_amount(cutted_plants):
	count = 0
	if len(cutted_plants) == 2:
		pesticide_min = cutted_plants[0][-1]
		length = len(cutted_plants[1])
		for i in range(1, length + 1):
			if pesticide_min >= cutted_plants[1][-i]:
				count += 1
			else:
				return length - count
	else:
		return 1

def die_plants(cutted_plants):
	plants = cutted_plants
	cutted_plants = [plants[0]]
	for i in range(1, len(plants)):
		plants_stack = plants[i]
		del plants_stack[0]
		if plants_stack != []:
			cutted_plants.append(plants_stack)
	return cutted_plants

def reset_plants(cutted_plants):
	plants = cutted_plants
	cutted_plants = []
	plants_stack = plants[0]
	for i in range(len(plants) - 1):
		if plants[i][-1] >= plants[i + 1][0]:
			plants_stack = plants_stack + plants[i + 1]
		else:
			cutted_plants.append(plants_stack)
			plants_stack = plants[i + 1]
	cutted_plants.append(plants_stack)
	return cutted_plants
n = int(input())
plants = [int(plant) for plant in input().strip().split()]
cutted_plants = []
day = 0
cutted_plants = cut_plants(plants)
while len(cutted_plants) != 1:
	after_day = check_plants_amount(cutted_plants)
	day = day + after_day
	if after_day != 1:
		break
	cutted_plants = die_plants(cutted_plants)
	cutted_plants = reset_plants(cutted_plants)
print(day)


num = int(input().strip())
plants = list(map(int, input().strip().split(' ')))
max_day = 0
days = [0] * num
kept = [0]
min_pes = plants[0]
for i in range(1, num):
	if plants[i] > plants[i - 1]:
		days[i] = 1
	min_pes = min(min_pes, plants[i])
	while len(kept) != 0 and plants[kept[-1]] >= plants[i]:
		if plants[i] > min_pes:
			days[i] = max(days[i], days[kept[-1]] + 1)
		kept.pop()
	max_day = max(max_day, days[i])
	kept.append(i)
print(max_day)


class Plant:

	def __init__(self, p, d):
		self.pesticide = p
		self.days = d
input()
stack = []
plants = [int(x) for x in input().split()]
days = 0
stack = []
maxDaysAlive = 0
for pesticide in plants:
	daysAlive = 0
	while stack and pesticide <= stack[-1].pesticide:
		daysAlive = max(daysAlive, stack.pop().days)
	if not stack:
		daysAlive = 0
	else:
		daysAlive += 1
	maxDaysAlive = max(maxDaysAlive, daysAlive)
	stack.append(Plant(pesticide, daysAlive))
print(maxDaysAlive)


import sys
n1 = input().strip().split(' ')
arr = [int(h1_temp) for h1_temp in input().strip().split(' ')]

class Plant:

	def __init__(self, pesticide, days):
		self.pesticide = pesticide
		self.days = days

def plants_days(a):
	stack = []
	max_days_alive = 0
	for pesticide in a:
		days_alive = 0
		while stack and pesticide <= stack[-1].pesticide:
			days_alive = max(days_alive, stack.pop().days)
		if not stack:
			days_alive = 0
		else:
			days_alive += 1
		max_days_alive = max(max_days_alive, days_alive)
		stack.append(Plant(pesticide, days_alive))
	return max_days_alive
print(plants_days(arr))


import sys

def top(stack):
	return stack[len(stack) - 1]
num_plants = int(input())
str_plants = input().split()
plants = list(map(int, str_plants))
max_days = 0
min = plants[0]
days = [0] * len(plants)
stack = []
for (index, plant) in enumerate(plants):
	if index == 0:
		continue
	if plant > plants[index - 1]:
		days[index] = 1
	min = min if min < plants[index] else plants[index]
	while stack and plants[top(stack)] >= plant:
		if plants[index] > min:
			if days[index] < days[top(stack)] + 1:
				days[index] = days[top(stack)] + 1
		i = stack.pop()
	if days[index] > max_days:
		max_days = days[index]
	stack.append(index)
print(max_days)


N = int(input())
p = list(map(int, input().split(' ')))
days = [0] * N
s = [0]
mi = p[0]
ma = 0
for i in range(1, N):
	if p[i] > p[i - 1]:
		days[i] = 1
	mi = min(mi, p[i])
	while s and p[s[-1]] >= p[i]:
		if p[i] > mi:
			days[i] = max(days[i], days[s[-1]] + 1)
		s.pop()
	ma = max(ma, days[i])
	s += [i]
print(ma)


N = int(input())
p = list(map(int, input().split(' ')))
days = [0] * N
s = [0]
mi = p[0]
ma = 0
for i in range(1, N):
	if p[i] > p[i - 1]:
		days[i] = 1
	mi = min(mi, p[i])
	while s and p[s[-1]] >= p[i]:
		if p[i] > mi:
			days[i] = max(days[i], days[s[-1]] + 1)
		s.pop()
	ma = max(ma, days[i])
	s += [i]
print(ma)


n = int(input())
plants = list(map(int, input().strip().split()))
idx = []
day = [0] * n
(min_p, res) = (plants[0], 0)
for i in range(1, n):
	if plants[i] > plants[i - 1]:
		day[i] = 1
	min_p = min(min_p, plants[i])
	while len(idx) != 0 and plants[idx[-1]] >= plants[i]:
		if plants[i] > min_p:
			day[i] = max(day[i], day[idx[-1]] + 1)
		idx.pop()
	res = max(res, day[i])
	idx.append(i)
print(res)


N = int(input())
p = list(map(int, input().split(' ')))
days = [0] * N
s = [0]
mi = p[0]
ma = 0
for i in range(1, N):
	if p[i] > p[i - 1]:
		days[i] = 1
	mi = min(mi, p[i])
	while s and p[s[-1]] >= p[i]:
		if p[i] > mi:
			days[i] = max(days[i], days[s[-1]] + 1)
		s.pop()
	ma = max(ma, days[i])
	s += [i]
print(ma)


import sys
data = sys.stdin.read()
data = data.splitlines()
n = int(data[0])
data = [int(x) for x in data[1].split(' ')]
days = [0] * n
peaks = []
mini = data[0]
tot_days = 0
if n == 0 or n == 1:
	print(0)
else:
	for i in range(1, n, 1):
		if data[i] > data[i - 1]:
			days[i] = 1
			peaks.append(i)
		elif data[i] > mini:
			while peaks and data[i] <= data[peaks[-1]]:
				days[i] = max(days[i], days[peaks[-1]] + 1)
				del peaks[-1]
			peaks.append(i)
		else:
			mini = data[i]
			peaks = []
		tot_days = max(tot_days, days[i])
print(tot_days)


N = int(input().strip())
poison = [int(temp) for temp in input().strip().split(' ')]
stack = []
stack_list = []
i = 1
while i < N:
	if i == N - 1 and poison[i] <= poison[i - 1]:
		stack.append(poison[i - 1])
		stack.append(poison[i])
		stack_list.append(stack)
		i += 1
	elif i == N - 1:
		stack.append(poison[i - 1])
		stack_list.append(stack)
		stack = [poison[i]]
		stack_list.append(stack)
		i += 1
	elif poison[i] <= poison[i - 1]:
		stack.append(poison[i - 1])
		i += 1
	else:
		stack.append(poison[i - 1])
		stack_list.append(stack)
		stack = []
		i += 1
max_iteration = 0
i = 1
while len(stack_list) > 1:
	stack_list[i].pop(0)
	if len(stack_list[i]) == 0:
		stack_list.pop(i)
		i -= 1
	elif len(stack_list) > 1 and stack_list[i][0] <= stack_list[i - 1][-1]:
		stack_list[i - 1].extend(stack_list.pop(i))
		i -= 1
	if i < len(stack_list) - 1:
		i += 1
	else:
		i = 1
		max_iteration += 1
print(max_iteration)


n = int(input().strip())
plist = [int(c) for c in input().strip().split(' ')]
stack = []
stack.append((0, -1))
maxdays = -1
for i in range(n):
	days = 1
	while stack:
		(pid, tdays) = stack[-1]
		if plist[pid] >= plist[i]:
			days = max(days, tdays + 1)
			stack.pop()
		else:
			break
	if not stack:
		days = -1
	maxdays = max(maxdays, days)
	stack.append((i, days))
print(maxdays if maxdays > 0 else 0)


N = int(input())
p = list(map(int, input().split(' ')))
days = [0] * N
s = [0]
mi = p[0]
ma = 0
for i in range(1, N):
	if p[i] > p[i - 1]:
		days[i] = 1
	mi = min(mi, p[i])
	while s and p[s[-1]] >= p[i]:
		if p[i] > mi:
			days[i] = max(days[i], days[s[-1]] + 1)
		s.pop()
	ma = max(ma, days[i])
	s += [i]
print(ma)


length = input()
arr = [int(_) for _ in input().strip().split()]
stack = [(arr[0], 0)]
stack_len = 1
max_day = 0
minimum = arr[0]

def calc_day(number, stack_row, max_temp_day):
	if number > stack_row[0]:
		if stack_row[1] == 0:
			return (True, max_temp_day + 1)
		if stack_row[1] > max_temp_day:
			return (True, max_temp_day + 1)
		elif stack_row[1] == max_temp_day:
			return (False, -1)
		else:
			return (False, -1)
	elif number == stack_row[0]:
		if stack_row[1] == 0:
			raise ValueError('IMpossible')
		if max_temp_day == 0:
			return (True, stack_row[1] + 1)
		if stack_row[1] > max_temp_day:
			return (True, stack_row[1] + 1)
		elif stack_row[1] == max_temp_day:
			return (False, -1)
		else:
			return (False, -1)
	else:
		return ValueError('IMpossible')

def get_dependent_element(number):
	counter = 1
	max_temp_day = 0
	while counter <= stack_len:
		stack_row = stack.pop()
		if number < stack_row[0]:
			pass
		else:
			day_row = calc_day(number, stack_row, max_temp_day)
			if day_row[0]:
				stack.append(stack_row)
				return day_row[1]
		max_temp_day = max(stack_row[1], max_temp_day)
		counter += 1
	return -2

def get_day(number):
	if number > stack[-1][0]:
		return 1
	else:
		return get_dependent_element(number)
for elem in arr[1:]:
	if elem <= minimum:
		(day, minimum) = (0, elem)
	else:
		day = get_day(elem)
		max_day = max(day, max_day)
	stack.append((elem, day))
	stack_len += 1
print(max_day)


class plant_node:

	def __init__(self, val, end_date):
		self.val = val
		self.end_date = end_date
N = int(input().strip())
plants = [int(val) for val in input().strip().split(' ')]
surviving_dict = dict()
surviving_stack = list()
stack_size = 0
for i in range(N):
	if stack_size == 0:
		surviving_dict[i] = 1
		surviving_stack.append(i)
		stack_size += 1
	elif plants[surviving_stack[stack_size - 1]] >= plants[i]:
		surviving_stack.append(i)
		stack_size += 1
		surviving_dict[i] = 1
answer_array = list()
dying_plants = list()
dying_size = 0
answer_size = 0
for i in range(N):
	if i in surviving_dict:
		answer_array.append(plant_node(plants[i], None))
		dying_plants.append(plant_node(plants[i], None))
		dying_size += 1
	else:
		current_end_date = 0
		while dying_size > 0:
			if dying_plants[dying_size - 1].end_date != None and dying_plants[dying_size - 1].end_date > current_end_date:
				if dying_plants[dying_size - 1].val < plants[i]:
					answer_array.append(plant_node(plants[i], current_end_date + 1))
					dying_plants.append(plant_node(plants[i], current_end_date + 1))
					dying_size += 1
					break
				else:
					current_end_date = dying_plants[dying_size - 1].end_date
					dying_plants.pop(dying_size - 1)
					dying_size -= 1
			elif dying_plants[dying_size - 1].end_date == None:
				answer_array.append(plant_node(plants[i], current_end_date + 1))
				dying_plants.append(plant_node(plants[i], current_end_date + 1))
				dying_size += 1
				break
			else:
				dying_plants.pop(dying_size - 1)
				dying_size -= 1
	answer_size += 1
largest_end_day = 0
for i in range(N):
	if answer_array[i].end_date != None:
		largest_end_day = max(largest_end_day, answer_array[i].end_date)
print(largest_end_day)


input()
arr = [int(x) for x in input().strip().split()]
stack = []
days = [0 for i in range(len(arr))]
max_time = 0
for i in range(len(arr)):
	x = None
	max_time = 0
	while stack != [] and arr[stack[-1]] >= arr[i]:
		x = stack.pop()
		max_time = max(max_time, days[x])
	if not stack:
		days[i] = 0
	elif not x:
		days[i] = 1
	else:
		days[i] = max_time + 1
	stack.append(i)
print(max(days))


N = int(input())
p = list(map(int, input().split(' ')))
days = [0] * N
s = [0]
mi = p[0]
ma = 0
for i in range(1, N):
	if p[i] > p[i - 1]:
		days[i] = 1
	mi = min(mi, p[i])
	while s and p[s[-1]] >= p[i]:
		if p[i] > mi:
			days[i] = max(days[i], days[s[-1]] + 1)
		s.pop()
	ma = max(ma, days[i])
	s += [i]
print(ma)


N = int(input())
p = list(map(int, input().split(' ')))
days = [0] * N
s = [0]
mi = p[0]
ma = 0
for i in range(1, N):
	if p[i] > p[i - 1]:
		days[i] = 1
	mi = min(mi, p[i])
	while s and p[s[-1]] >= p[i]:
		if p[i] > mi:
			days[i] = max(days[i], days[s[-1]] + 1)
		s.pop()
	ma = max(ma, days[i])
	s += [i]
print(ma)


nr_plants = int(input())
hi = 0
stack = []
for p in map(int, input().strip().split()):
	nd = 1
	while stack:
		(q, n) = stack[-1]
		if q >= p:
			nd = n + 1
			stack.pop()
		elif nd > n:
			stack.pop()
		else:
			stack.append((p, nd))
			hi = max(hi, nd)
			break
	else:
		stack.append((p, nr_plants + 1))
print(hi)


class Plant:

	def __init__(self, level):
		self.killed = 0
		self.level = level

def days_til_stability(pesticide_levels):
	plants = [Plant(level) for level in pesticide_levels]
	n = len(plants)
	i = n - 1
	best = 0
	stack = []
	while i > -1:
		p = plants[i]
		if not stack or p.level >= stack[-1].level:
			stack.append(p)
			i -= 1
		else:
			target = stack.pop()
			if target.killed > p.killed:
				p.killed = target.killed
			else:
				p.killed += 1
			best = max(p.killed, best)
	return best
n = int(input().strip())
pest_levels = [int(l) for l in input().strip().split()]
print(days_til_stability(pest_levels))


n = int(input())
plants = [int(i) for i in input().split(' ')]
stack = []
maxDays = 0
for i in range(0, len(plants)):
	plant = plants[i]
	mdays = 0
	while len(stack) != 0 and stack[len(stack) - 1][0] >= plant:
		otherPlant = stack.pop()
		mdays = max(otherPlant[1], mdays)
	days = mdays + 1 if len(stack) != 0 else 0
	stack.append((plant, days))
	maxDays = max(days, maxDays)
print(maxDays)


from collections import namedtuple
Item = namedtuple('Point', ['p', 'l'])
plants = []
n = int(input().strip())
p = list(map(int, input().strip().split()))
result = 0
for i in range(n):
	if plants:
		previous = plants[-1]
		if previous.p >= p[i]:
			if previous.l == 0:
				plants.append(Item(p[i], 0))
				continue
			else:
				l = previous.l
				while 0 != plants[-1].l and (plants[-1].p >= p[i] or plants[-1].l == l):
					l = plants[-1].l
					plants.pop()
				if plants[-1].p < p[i]:
					l += 1
				if l > result:
					result = l
				if 0 == plants[-1].l and plants[-1].p >= p[i]:
					l = 0
				plants.append(Item(p[i], l))
		else:
			plants.append(Item(p[i], 1))
			if 0 == result:
				result = 1
	else:
		plants.append(Item(p[i], 0))
print(result)


from collections import deque
N = int(input().strip())
plants = list(map(int, input().strip().split()))
l = []
st = deque([plants[0]])
for i in range(1, len(plants)):
	if st and st[-1] < plants[i]:
		l.append(st)
		st = deque([plants[i]])
	else:
		st.append(plants[i])
else:
	if st:
		l.append(st)
c = 0
while len(l) > 1:
	c += 1
	new_l = [l[0]]
	for i in range(1, len(l)):
		st = l[i]
		st.popleft()
		if st and new_l[-1][-1] >= st[0]:
			new_l[-1].extend(st)
		elif st:
			new_l.append(st)
	l = new_l
print(c)


n = int(input())
plants = [int(x) for x in input().split(' ')]
stack = []
maxDays = 0
for i in range(len(plants)):
	current = plants[i]
	maxTemp = 0
	while len(stack) > 0 and stack[len(stack) - 1][0] >= current:
		prev = stack.pop()
		maxTemp = max(prev[1], maxTemp)
	days = maxTemp + 1 if len(stack) > 0 else 0
	stack.append((current, days))
	maxDays = max(days, maxDays)
print(maxDays)


import sys
sys.stdin.readline()
plants = list(map(int, sys.stdin.readline().split(' ')))
stack = []
maxDays = 0
for i in range(0, len(plants)):
	plant = plants[i]
	mdays = 0
	while len(stack) != 0 and stack[len(stack) - 1][0] >= plant:
		otherPlant = stack.pop()
		mdays = max(otherPlant[1], mdays)
	days = mdays + 1 if len(stack) != 0 else 0
	stack.append((plant, days))
	maxDays = max(days, maxDays)
print(maxDays)


N = int(input())
plants = [int(x) for x in input().strip().split()]
plants_stack = []
max_days = 0
for i in range(len(plants)):
	curr_max_days = 0
	while len(plants_stack) > 0 and plants_stack[len(plants_stack) - 1]['val'] >= plants[i]:
		curr_max_days = max(curr_max_days, plants_stack.pop()['days'])
	curr_max_days += 1 if len(plants_stack) != 0 else 0
	plants_stack.append({'val': plants[i], 'days': curr_max_days})
	max_days = max(max_days, curr_max_days)
print(max_days)


n = int(input())
p = [int(s) for s in input().split()]

class Plant:

	def __init__(self, pest, life):
		self.pest = pest
		self.life = life
		self.delay = 1
stack = [Plant(p[0], -1)]
max_life = 0
for i in p[1:]:
	while i <= stack[-1].pest:
		if stack[-1].life < 0:
			stack.append(Plant(i, -1))
			break
		else:
			stack.pop()
	else:
		curr_plant = Plant(i, stack[-1].delay)
		max_life = max(max_life, stack[-1].delay)
		if stack[-1].life == 1:
			stack.pop()
		else:
			stack[-1].delay += 1
			stack[-1].life -= 1
		stack.append(curr_plant)
print(max_life)


n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
stack = []
prev = 0
for i in range(1, len(a)):
	if a[i] > a[i - 1]:
		stack.append(a[prev:i])
		prev = i
stack.append(a[prev:])
days = 0
while len(stack) > 1:
	for i in range(1, len(stack)):
		stack[i].pop(0)
	i = 0
	while i < len(stack):
		if len(stack[i]) == 0:
			stack.pop(i)
		else:
			i += 1
	i = 1
	while i < len(stack):
		if stack[i][0] <= stack[i - 1][len(stack[i - 1]) - 1]:
			stack[i - 1].extend(stack[i])
			stack.pop(i)
		else:
			i += 1
	days += 1
print(days)


class Plant:

	def __init__(self, pesticide, days):
		self.pesticide = pesticide
		self.days = days

def solvePlants(a):
	stack = []
	maxDaysAlive = 0
	for pesticide in a:
		daysAlive = 0
		while stack and pesticide <= stack[-1].pesticide:
			daysAlive = max(daysAlive, stack.pop().days)
		if not stack:
			daysAlive = 0
		else:
			daysAlive += 1
		maxDaysAlive = max(maxDaysAlive, daysAlive)
		stack.append(Plant(pesticide, daysAlive))
	print(maxDaysAlive)

def main():
	N = input()
	numbers = map(int, input().split())
	solvePlants(numbers)
main()


import sys
n = int(input())
pesticideValues = [int(x) for x in input().split(' ')]
meToMyRight = {0: 1}
meToMyLeft = {}
for plantIndex in range(1, n):
	meToMyLeft[plantIndex] = plantIndex - 1
	meToMyRight[plantIndex] = plantIndex + 1
del meToMyRight[n - 1]
numDaysWhereThingsWillChange = 0
plantsThatWillDieToday = set()
plantsThatWillDieTomorrow = set()
for plant in meToMyLeft.keys():
	if pesticideValues[plant] > pesticideValues[meToMyLeft[plant]]:
		plantsThatWillDieToday.add(plant)
while True:
	plantsThatWillDieTomorrow = set()
	if plantsThatWillDieToday:
		numDaysWhereThingsWillChange += 1
	for plantThatWillDieToday in reversed(sorted(plantsThatWillDieToday)):
		plantToRight = None
		plantToLeft = meToMyLeft[plantThatWillDieToday]
		if meToMyRight.get(plantThatWillDieToday):
			plantToRight = meToMyRight[plantThatWillDieToday]
			meToMyRight[plantToLeft] = plantToRight
			meToMyLeft[plantToRight] = plantToLeft
			if pesticideValues[plantToRight] > pesticideValues[plantToLeft]:
				plantsThatWillDieTomorrow.add(plantToRight)
			del meToMyRight[plantThatWillDieToday]
		else:
			del meToMyRight[plantToLeft]
		del meToMyLeft[plantThatWillDieToday]
	if plantsThatWillDieTomorrow:
		plantsThatWillDieToday = plantsThatWillDieTomorrow
	else:
		print(numDaysWhereThingsWillChange)
		sys.exit(0)


def chain_maker(l):
	chains = []
	n = len(l)
	ans = [l[0]]
	if n == 1:
		return ans
	else:
		for i in range(n - 1):
			if l[i] >= l[i + 1]:
				ans.append(l[i + 1])
			else:
				chains.append(list(reversed(ans)))
				ans = [l[i + 1]]
		chains.append(list(reversed(ans)))
		return chains
N = int(input())
P = [int(x) for x in input().split(' ')]
ListOfChains = chain_maker(P)
Days = 0
while len(ListOfChains) != 1:
	for i in range(len(ListOfChains) - 1):
		ListOfChains[i + 1].pop()
	i = 0
	while i < len(ListOfChains) - 1:
		if ListOfChains[i + 1] == []:
			del ListOfChains[i + 1]
		elif ListOfChains[i + 1][-1] <= ListOfChains[i][0]:
			ListOfChains[i] = ListOfChains[i + 1] + ListOfChains[i]
			del ListOfChains[i + 1]
		else:
			i += 1
	Days += 1
print(Days)


n = int(input().strip())
p = list(map(int, input().strip().split(' ')))
dead = []
max_dead_days = 0
last_alive = float('inf')
prev = 0
for plant in p:
	if not dead:
		if plant <= last_alive:
			last_alive = plant
		elif plant > prev:
			dead.append([plant, 1])
		else:
			dead.append([plant, max_dead_days + 1])
	elif prev < plant:
		dead.append([plant, 1])
	else:
		while dead and dead[-1][0] >= plant:
			last_dead_plant = dead.pop()
			if last_dead_plant[1] > dead_days:
				dead_days = last_dead_plant[1]
			max_dead_days = dead_days if dead_days > max_dead_days else max_dead_days
		if dead and dead[-1][0] < plant:
			dead.append([plant, dead_days + 1])
		elif not dead:
			if plant > last_alive:
				dead.append([plant, min(max_dead_days + 1, dead_days + 1)])
			else:
				last_alive = plant
	prev = plant
	dead_days = 0
while dead:
	dead_days = dead.pop()[1]
	max_dead_days = dead_days if dead_days > max_dead_days else max_dead_days
print(max_dead_days)


n = int(input())
a = list(map(int, input().split()))
b = [[a[0]]]
for i in range(1, len(a)):
	if a[i - 1] >= a[i]:
		b[-1].append(a[i])
	else:
		b.append([a[i]])
c = 0
while len(b) > 1:
	c += 1
	for i in range(len(b) - 1, 0, -1):
		if b[i - 1][-1] < b[i][0]:
			b[i].pop(0)
			if len(b[i]) == 0:
				b.pop(i)
			elif b[i - 1][-1] >= b[i][0]:
				b[i - 1].extend(b[i])
				b.pop(i)
		else:
			b[i - 1].extend(b[i])
			b.pop(i)
print(c)


import sys

class Plant:

	def __init__(self, pesticide, days):
		self.pesticide = pesticide
		self.days = days

	def __str__(self):
		return ('plant ', self.pesticide, ' - ', self.days)

def printStack(s):
	counter = 0
	for p in s:
		counter += 1

def solvePlants(a):
	stack = []
	maxDaysAlive = 0
	for pesticide in a:
		daysAlive = 0
		while stack and pesticide <= stack[-1].pesticide:
			daysAlive = max(daysAlive, stack.pop().days)
		if not stack:
			daysAlive = 0
		else:
			daysAlive += 1
		maxDaysAlive = max(maxDaysAlive, daysAlive)
		stack.append(Plant(pesticide, daysAlive))
	print(maxDaysAlive)

def main():
	n = int(input().strip())
	plants = list(map(int, input().strip().split(' ')))
	solvePlants(plants)
main()


N = int(input())
A = list(map(int, input().strip().split(' ')))
StackX = []
max_days = 0
for a1 in range(N):
	plant = A[a1]
	mdays = 0
	while len(StackX) != 0 and StackX[len(StackX) - 1][0] >= plant:
		TempPlant = StackX.pop()
		mdays = max(TempPlant[1], mdays)
	if len(StackX) != 0:
		days = mdays + 1
	else:
		days = 0
	StackX.append((plant, days))
	max_days = max(days, max_days)
print(max_days)


N = int(input())
A = [int(s) for s in input().split()]
stack = []
days_till_deaths = []
max_days_till_death = 0
for x in A:
	block = 0
	while stack and stack[-1] >= x:
		stack.pop()
		block = max(block, days_till_deaths.pop())
	if stack:
		stack.append(x)
		days_till_deaths.append(block + 1)
		max_days_till_death = max(max_days_till_death, block + 1)
	else:
		stack.append(x)
		days_till_deaths.append(0)
print(max_days_till_death)


N = int(input())
p = list(map(int, input().split()))
p.reverse()
s = []
temp = 0
m = 0
for e in p:
	while s and s[-1][0] > e:
		temp = s.pop()
		m = max(m, temp[1])
		if len(s) > 0:
			s[-1][1] = max(temp[1] + 1, s[-1][1])
	s.append([e, 0])
if len(s) == N:
	print(0)
else:
	print(m + 1)


_ = input()
no_of_days = 0
stack = []
maxDays = 0
plants = list(map(int, input().split()))
for i in range(len(plants)):
	plant = plants[i]
	mdays = 0
	while len(stack) != 0 and stack[len(stack) - 1][0] >= plant:
		otherPlant = stack.pop()
		mdays = max(otherPlant[1], mdays)
	days = mdays + 1 if len(stack) != 0 else 0
	stack.append((plant, days))
	maxDays = max(days, maxDays)
print(maxDays)


n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
a = [-1] + a
p = [0] * (n + 1)
s = [[1, -1]]
ans = 0
for i in range(2, n + 1):
	t = i - 1
	while a[t] >= a[i]:
		t = p[t]
	p[i] = t
	d = 1
	while s and t < s[-1][0]:
		d = s[-1][1] + 1
		s.pop()
	if not s:
		s.append([i, -1])
	else:
		while s and s[-1][1] != -1 and (d >= s[-1][1]):
			s.pop()
		s.append([i, d])
	if ans < d:
		ans = d
print(ans)


num_plants = int(input())
plants = list(map(int, input().split()))
stack = []
max_days = 0
for pests in plants:
	days = 0
	while stack:
		other = stack.pop()
		if other[0] < pests:
			stack.append(other)
			days += 1
			break
		else:
			days = max(days, other[1])
	stack.append((pests, days))
	max_days = max(days, max_days)
print(max_days)


class Plant:

	def __init__(self, pesticide, days):
		self.pesticide = pesticide
		self.days = days

def solvePlants(a):
	stack = []
	maxDaysAlive = 0
	for pesticide in a:
		daysAlive = 0
		while stack and pesticide <= stack[-1].pesticide:
			daysAlive = max(daysAlive, stack.pop().days)
		if not stack:
			daysAlive = 0
		else:
			daysAlive += 1
		maxDaysAlive = max(maxDaysAlive, daysAlive)
		stack.append(Plant(pesticide, daysAlive))
	print(maxDaysAlive)

def main():
	N = input()
	numbers = [int(x) for x in input().split()]
	solvePlants(numbers)
main()


n = int(input())
plants = list(map(int, input().split(' ')))
s = []
maxDays = 0
for i in range(0, len(plants)):
	plant = plants[i]
	mdays = 0
	while len(s) != 0 and s[len(s) - 1][0] >= plant:
		otherPlant = s.pop()
		mdays = max(otherPlant[1], mdays)
	if len(s) != 0:
		days = mdays + 1
	else:
		days = 0
	s.append((plant, days))
	maxDays = max(days, maxDays)
print(maxDays)


from collections import deque

class StackNode(object):

	def __init__(self, value):
		self.value = value
		self.next = None
		self.prev = None

	def __repr__(self):
		return str(self.value)

class Stack(object):

	def __init__(self):
		self.head = None
		self.tail = None

	def pop(self):
		value = None
		if self.head:
			value = self.head.value
			self.head = self.head.prev
			if self.head is not None:
				self.head.next = None
		if not self.head:
			self.tail = None
		return value

	def push(self, value):
		node = StackNode(value)
		if not self.head:
			self.head = node
			self.tail = node
		else:
			self.head.next = node
			node.prev = self.head
			self.head = node

	def push_tail(self, value):
		node = StackNode(value)
		if not self.tail:
			self.tail = node
			self.head = node
		else:
			self.tail.prev = node
			node.next = self.tail
			self.tail = node

	def peek(self):
		value = None
		if self.head:
			value = self.head.value
		return value

	def peek_base(self):
		value = None
		if self.tail:
			value = self.tail.value
		return value

	def empty(self):
		return self.head is None

	def merge(self, stack):
		self.head.next = stack.tail
		stack.tail.prev = self.head
		self.head = stack.head

	def __repr__(self):
		item_list = []
		node = self.tail
		while node is not None:
			item_list.append(str(node))
			node = node.next
		return str(item_list)

def days_till_no_plants_die(plants):
	stacks = deque()
	index = 0
	num_plants = len(plants)
	while index < num_plants:
		plant = plants[index]
		current_stack = Stack()
		current_stack.push(plant)
		last_plant = plant
		next_plant_index = 1
		while index + next_plant_index < num_plants and plants[index + next_plant_index] <= last_plant:
			last_plant = plants[index + next_plant_index]
			current_stack.push_tail(last_plant)
			next_plant_index += 1
		index += next_plant_index
		stacks.append(current_stack)
	num_stacks = len(stacks)
	num_days = 0
	while num_stacks > 1:
		popped_stacks = deque()
		for i in range(0, num_stacks):
			stack = stacks[i]
			if i != 0:
				stack.pop()
			if not stack.empty():
				popped_stacks.append(stack)
		stacks = popped_stacks
		num_stacks = len(stacks)
		new_stacks = deque()
		while stacks:
			stack = stacks.popleft()
			next_stack = None
			if not stacks:
				new_stacks.append(stack)
				continue
			next_stack = stacks.popleft()
			if stack.peek_base() >= next_stack.peek():
				next_stack.merge(stack)
				stack = next_stack
				stacks.appendleft(stack)
			else:
				stacks.appendleft(next_stack)
				new_stacks.append(stack)
		stacks = new_stacks
		num_stacks = len(stacks)
		num_days += 1
	return num_days
num_plants = int(input())
plants = [int(x) for x in input().strip().split()]
print(days_till_no_plants_die(plants))


class Node:

	def __init__(self, data):
		self.data = data
		self.count = 0
		self.next = None

class Stack:

	def __init__(self):
		self.top = None

	def __str__(self):
		output = ''
		node = self.top
		while node != None:
			output += str(node.data) + ' '
			node = node.next
		return output[:-1]

	def push(self, node):
		node.next = self.top
		self.top = node

	def pop(self):
		node = self.top
		self.top = node.next
		node.next = None
		return node
N = int(input())
P = [int(i) for i in input().split(' ')]
stack = Stack()
mx = 0
for p in P[::-1]:
	node = Node(p)
	count = 0
	while stack.top != None and p < stack.top.data:
		tp = stack.pop()
		if tp.count > count:
			count = tp.count
		elif tp.count <= count:
			count += 1
	node.count = count
	stack.push(node)
	if count > mx:
		mx = count
print(mx)


n = int(input().strip())
P = list(map(int, input().strip().split(' ')))
S = [(P[0], 0)]
max_days = 0
for i in range(1, len(P), 1):
	p_i = P[i]
	(p_h, d_h) = S.pop()
	if p_i > p_h:
		d_i = 1
		if d_h > d_i or d_h == 0:
			S.append((p_h, d_h))
		S.append((p_i, d_i))
		max_days = max(max_days, d_i)
	elif p_i == p_h:
		d_i = d_h + 1 if d_h > 0 else 0
		if len(S) > 0:
			(p_g, d_g) = S.pop()
			if d_g > d_i or d_g == 0:
				S.append((p_g, d_g))
		S.append((p_i, d_i))
		max_days = max(max_days, d_i)
	elif p_i < p_h:
		d_i = d_h + 1 if d_h > 0 else 0
		while len(S) > 0:
			(p_g, d_g) = S.pop()
			if p_i > p_g:
				if d_g > d_i or d_g == 0:
					S.append((p_g, d_g))
				S.append((p_i, d_i))
				max_days = max(max_days, d_i)
				break
			elif p_i == p_g:
				d_i = max(d_i, d_g + 1) if d_g > 0 else 0
				if len(S) > 0:
					(p_f, d_f) = S.pop()
					if d_f > d_i or d_f == 0:
						S.append((p_f, d_f))
				S.append((p_i, d_i))
				max_days = max(max_days, d_i)
				break
			elif p_i < p_g:
				d_i = d_g + 1 if d_g > 0 else 0
				continue
		if len(S) == 0:
			d_i = 0
			S.append((p_i, d_i))
print(max_days)


def Poisonous_Plants():
	_ = input()
	plants = list(map(int, input().split()))
	stack = [[plants[0]]]
	k = 1
	while k < len(plants):
		while k < len(plants) and stack[-1][-1] >= plants[k]:
			stack[-1].append(plants[k])
			k += 1
		if k < len(plants):
			stack.append([plants[k]])
			k += 1
	c = 0
	countDel = 1
	while countDel > 0:
		countDel = 0
		for i in range(len(stack) - 1, 0, -1):
			if stack[i - 1][-1] < stack[i][0]:
				stack[i].pop(0)
				countDel += 1
			if not stack[i]:
				stack.pop(i)
		c += 1 if countDel > 0 else 0
	print(c)
Poisonous_Plants()


import sys

class Plant:

	def __init__(self, pesticide, days):
		self.pesticide = pesticide
		self.days = days

def solvePlants(a):
	stack = []
	maxDaysAlive = 0
	for pesticide in a:
		daysAlive = 0
		while stack and pesticide <= stack[-1].pesticide:
			daysAlive = max(daysAlive, stack.pop().days)
		if not stack:
			daysAlive = 0
		else:
			daysAlive += 1
		maxDaysAlive = max(maxDaysAlive, daysAlive)
		stack.append(Plant(pesticide, daysAlive))
	print(maxDaysAlive)
N = input()
numbers = list(map(int, input().split()))
solvePlants(numbers)


N = int(input())
p = list(map(int, input().split(' ')))
days = [0] * N
s = [0]
mi = p[0]
ma = 0
for i in range(1, N):
	if p[i] > p[i - 1]:
		days[i] = 1
	mi = min(mi, p[i])
	while s and p[s[-1]] >= p[i]:
		if p[i] > mi:
			days[i] = max(days[i], days[s[-1]] + 1)
		s.pop()
	ma = max(ma, days[i])
	s += [i]
print(ma)


num_plants = int(input())
pest_map = map(lambda x: int(x), input().strip().split(' '))
pest_counts = list(pest_map)
stack = []
best = 0
for pest in pest_counts:
	days_alive = 0
	while stack and pest <= stack[-1][0]:
		(top_plant, top_days) = stack.pop()
		if top_days > days_alive:
			days_alive = top_days
	if stack:
		days_alive += 1
	else:
		days_alive = 0
	if best < days_alive:
		best = days_alive
	stack.append((pest, days_alive))
print(best)


N = int(input())
p = list(map(int, input().split(' ')))
days = [0] * N
s = [0]
mi = p[0]
ma = 0
for i in range(1, N):
	if p[i] > p[i - 1]:
		days[i] = 1
	mi = min(mi, p[i])
	while s and p[s[-1]] >= p[i]:
		if p[i] > mi:
			days[i] = max(days[i], days[s[-1]] + 1)
		s.pop()
	ma = max(ma, days[i])
	s += [i]
print(ma)


plant_count = int(input().strip())
plants = [int(value) for value in input().strip().split()]
stacks = [[float('inf')]]
for plant in plants:
	if plant > stacks[-1][-1]:
		stacks.append([plant])
	else:
		stacks[-1].append(plant)
del stacks[0][0]
days = 0
while len(stacks) > 1:
	for i in range(len(stacks) - 1, 0, -1):
		del stacks[i][0]
		if not stacks[i]:
			del stacks[i]
	for i in range(len(stacks) - 1, 0, -1):
		if stacks[i][0] <= stacks[i - 1][-1]:
			stacks[i - 1] += stacks[i]
			del stacks[i]
	days += 1
print(days)


from collections import deque
(_, plants) = (input(), [int(x) for x in input().split()])
queues = deque([deque([plants[0]])])
for i in range(1, len(plants)):
	plant = plants[i]
	if plant <= queues[-1][-1]:
		queues[-1].append(plant)
	else:
		queues.append(deque([plant]))
count = 0
while len(queues) > 1:
	new_queues = deque([queues.popleft()])
	while queues:
		next_queue = queues.popleft()
		next_queue.popleft()
		if not next_queue:
			continue
		elif next_queue[0] <= new_queues[-1][-1]:
			while next_queue:
				new_queues[-1].append(next_queue.popleft())
		else:
			new_queues.append(next_queue)
	count += 1
	queues = new_queues
print(count)


N = int(input())
p = list(map(int, input().split(' ')))
days = [0] * N
s = [0]
mi = p[0]
ma = 0
for i in range(1, N):
	if p[i] > p[i - 1]:
		days[i] = 1
	mi = min(mi, p[i])
	while s and p[s[-1]] >= p[i]:
		if p[i] > mi:
			days[i] = max(days[i], days[s[-1]] + 1)
		s.pop()
	ma = max(ma, days[i])
	s += [i]
print(ma)


no_flowers = int(input())
plants = list(map(int, input().split()))
stack = []
maxDays = 0
for i in range(0, len(plants)):
	plant = plants[i]
	mdays = 0
	while len(stack) != 0 and stack[len(stack) - 1][0] >= plant:
		otherPlant = stack.pop()
		mdays = max(otherPlant[1], mdays)
	days = mdays + 1 if len(stack) != 0 else 0
	stack.append((plant, days))
	maxDays = max(days, maxDays)
print(maxDays)


input()
p = [int(x) for x in input().split()]
S = [[p[-1]]]
for x in reversed(p[:-1]):
	if x < S[-1][-1]:
		S.append([])
	S[-1].append(x)
days = 0
while len(S) > 1:
	stop = True
	for i in range(0, len(S) - 1):
		S[i].pop()
	newS = [S[0]]
	for i in range(1, len(S)):
		if newS[-1] == [] or S[i] == [] or newS[-1][-1] <= S[i][0]:
			newS[-1].extend(S[i])
			stop = False
		else:
			newS.append(S[i])
	days += 1
	S = newS
print(days)


N = int(input())
plants = list(map(int, input().split()))
stack = []
maxDays = 0
for i in range(0, len(plants)):
	plant = plants[i]
	mdays = 0
	while len(stack) != 0 and stack[len(stack) - 1][0] >= plant:
		otherPlant = stack.pop()
		mdays = max(otherPlant[1], mdays)
	days = mdays + 1 if len(stack) != 0 else 0
	stack.append((plant, days))
	maxDays = max(days, maxDays)
print(maxDays)


import sys
n = int(input().strip())
P = [int(p) for p in input().strip().split(' ')]
max_d = 0
d = 0
S = []
prev = P[0]
for p in P[1:]:
	if p > prev:
		S.append((d, prev))
		d = 1
	else:
		d += 1
		while S and p <= S[-1][1]:
			(d_last, p_last) = S.pop()
			d = max(d, d_last + 1)
		if not S:
			d = 0
	max_d = max(max_d, d)
	prev = p
print(max_d)


class Plant:

	def __init__(self, pesticide, days):
		self.pesticide = pesticide
		self.days = days

def solve(a):
	stack = []
	maxDaysAlive = 0
	for pesticide in a:
		daysAlive = 0
		while stack and pesticide <= stack[-1].pesticide:
			daysAlive = max(daysAlive, stack.pop().days)
		if not stack:
			daysAlive = 0
		else:
			daysAlive += 1
		maxDaysAlive = max(maxDaysAlive, daysAlive)
		stack.append(Plant(pesticide, daysAlive))
	print(maxDaysAlive)

def main():
	N = input()
	numbers = map(int, input().split())
	solve(numbers)
main()


N = int(input())
p = list(map(int, input().split()))
days = [0] * N
s = [0]
mi = p[0]
ma = 0
for i in range(1, N):
	if p[i] > p[i - 1]:
		days[i] = 1
	mi = min(mi, p[i])
	while s and p[s[-1]] >= p[i]:
		if p[i] > mi:
			days[i] = max(days[i], days[s[-1]] + 1)
		s.pop()
	ma = max(ma, days[i])
	s += [i]
print(ma)


from math import inf

def solution(pepticides):
	days = 0
	survived = []
	deads = []
	for p in pepticides:
		if not survived or survived[-1] >= p:
			survived.append(p)
			days = max(days, count_days(deads))
			deads = []
		else:
			assert survived
			assert survived[-1] < p
			deads.append(p)
	else:
		days = max(days, count_days(deads))
	return days

def count_days(deads):
	if not deads:
		return 0
	assert len(deads) >= 1
	stack = [(deads.pop(0), 1)]
	for p in deads:
		days = 1
		while stack and stack[-1][0] >= p:
			(_, _days) = stack.pop(-1)
			days = 1 + _days
		while stack and stack[-1][1] <= days:
			stack.pop(-1)
		stack.append((p, days))
	return stack[0][1]

def main():
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	print(solution(arr))
main()


N = int(input())
p = list(map(int, input().split(' ')))
days = [0] * N
s = [0]
mi = p[0]
ma = 0
for i in range(1, N):
	if p[i] > p[i - 1]:
		days[i] = 1
	mi = min(mi, p[i])
	while s and p[s[-1]] >= p[i]:
		if p[i] > mi:
			days[i] = max(days[i], days[s[-1]] + 1)
		s.pop()
	ma = max(ma, days[i])
	s += [i]
print(ma)


import sys
sys.stdin.readline()
plants = list(map(int, input().strip().split(' ')))
stack = []
maxDays = 0
for i in range(0, len(plants)):
	plant = plants[i]
	mdays = 0
	while len(stack) != 0 and stack[len(stack) - 1][0] >= plant:
		otherPlant = stack.pop()
		mdays = max(otherPlant[1], mdays)
	days = mdays + 1 if len(stack) != 0 else 0
	stack.append((plant, days))
	maxDays = max(days, maxDays)
print(maxDays)


import sys
from filecmp import cmp
from os import linesep
from time import time

def process_gen(G):
	stack = []
	push = stack.append
	pop = stack.pop
	peek = lambda : stack[-1]

	def clear():
		del stack[:]
		return
	blockmin = None
	height = 0
	for m in G:
		if blockmin is None:
			blockmin = m
			continue
		if m <= blockmin:
			yield height
			height = 0
			clear()
			blockmin = m
			continue
		level = -1
		while stack and m <= peek()[0]:
			(_, level) = pop()
		if not stack:
			height += 1
		elif peek()[1] == level + 1:
			pop()
		push((m, level + 1))
	yield height

def test(num=None):
	if num is None:
		inp = sys.stdin
		out = sys.stdout
	else:
		inp = open('./input' + num + '.txt')
		out = open('./myoutput' + num + '.txt', 'w')
	start_time = time()
	N = int(inp.readline())
	G = map(int, inp.readline().strip().split(' '))
	print(max(process_gen(G)), file=out)
	end_time = time()
	if num is not None:
		inp.close()
		remove_chars = len(linesep)
		out.truncate(out.tell() - remove_chars)
		out.close()
		succeeded = cmp('myoutput' + num + '.txt', 'output' + num + '.txt')
		outcome = '  Success' if succeeded else '  Failure'
		print('#' + num + outcome + ' N', N, 'in {:f}s'.format(end_time - start_time))
test()


N = int(input())
p = list(map(int, input().split(' ')))
days = [0] * N
s = [0]
mi = p[0]
ma = 0
for i in range(1, N):
	if p[i] > p[i - 1]:
		days[i] = 1
	mi = min(mi, p[i])
	while s and p[s[-1]] >= p[i]:
		if p[i] > mi:
			days[i] = max(days[i], days[s[-1]] + 1)
		s.pop()
	ma = max(ma, days[i])
	s += [i]
print(ma)


from collections import deque
input()
List = list(map(int, input().split()))
Temp = []
count = -1
for i in List:
	if len(Temp) == 0 or Temp[count][-1] < i:
		Temp.append(deque())
		count += 1
		Temp[count].append(i)
	else:
		Temp[count].append(i)
days = 0
n = len(Temp)
while True:
	if len(Temp) == 1:
		break
	i = 1
	while i <= n - 1:
		Temp[i].popleft()
		if len(Temp[i]) == 0:
			del Temp[i]
			n -= 1
			i -= 1
		elif Temp[i][0] <= Temp[i - 1][-1]:
			Temp[i - 1].extend(list(Temp[i]))
			del Temp[i]
			n -= 1
			i -= 1
		i += 1
	days += 1
print(days)


input()
plantlist = [int(plant) for plant in input().split()]
N = len(plantlist)
maxdeath = 0
pdstack = [0] * N
pdstack[0] = [plantlist[0], N]
L = 1
for n in range(1, N):
	if plantlist[n] > pdstack[L - 1][0]:
		pdstack[L] = [plantlist[n], 1]
		maxdeath = max(maxdeath, 1)
		L += 1
	else:
		deathtimer = 1
		while L > 0 and plantlist[n] <= pdstack[L - 1][0]:
			deathtimer = max(deathtimer, pdstack[L - 1][1] + 1)
			L -= 1
		pdstack[L] = [plantlist[n], deathtimer]
		L += 1
		if L > 1:
			maxdeath = max(maxdeath, deathtimer)
print(maxdeath)


n = int(input())
plants = [int(n) for n in input().split(' ')]
lists = [[plants[0]]]
i = 0
count = 0
flag = 1
for x in range(1, len(plants)):
	if plants[x] <= plants[x - 1]:
		lists[i].append(plants[x])
	else:
		i += 1
		lists.append([plants[x]])
if len(lists) == 1:
	flag = 0
while flag == 1:
	l = len(lists)
	result = [lists[0]]
	for x in range(1, l):
		lists[x].pop(0)
		if len(lists[x]) != 0:
			result.append(lists[x])
	lists = []
	if len(result) == 1:
		count += 1
		break
	i = 0
	for x in range(1, len(result)):
		if x == 1:
			if result[x - 1][-1] >= result[x][0]:
				lists.append(result[x - 1] + result[x])
			else:
				lists.append(result[x - 1])
				lists.append(result[x])
				i += 1
		elif result[x - 1][-1] >= result[x][0]:
			lists[i] = lists[i] + result[x]
		else:
			i += 1
			lists.append(result[x])
	count += 1
	if len(lists) == 1:
		break
	result = []
print(count)


N = int(input())
ps = list(map(int, input().split()))
lives = [N] * N
kills = [0] * N
stack = list()
for (i, p) in enumerate(ps):
	while stack and ps[stack[-1]] >= p:
		stack.pop()
	if stack:
		killer = stack[-1]
		kills[killer] += 1
		lives[i] = kills[killer]
		lives[killer] -= 1
		if lives[killer] == 0:
			stack.pop()
	stack.append(i)
print(max(kills))