There are n psychos standing in a line. Each psycho is assigned a unique integer from 1 to n. At each step every psycho who has an id greater than the psycho to his right (if exists) kills his right neighbor in the line. Note that a psycho might kill and get killed at the same step. 

You're given the initial arrangement of the psychos in the line. Calculate how many steps are needed to the moment of time such, that nobody kills his neighbor after that moment. Look notes to understand the statement more precise.


-----Input-----

The first line of input contains integer n denoting the number of psychos, (1 ≤ n ≤ 10^5). In the second line there will be a list of n space separated distinct integers each in range 1 to n, inclusive — ids of the psychos in the line from left to right.


-----Output-----

Print the number of steps, so that the line remains the same afterward.


-----Examples-----
Input
10
10 9 7 8 6 5 3 4 2 1

Output
2

Input
6
1 2 3 4 5 6

Output
0



-----Note-----

In the first sample line of the psychos transforms as follows: [10 9 7 8 6 5 3 4 2 1]  →  [10 8 4]  →  [10]. So, there are two steps.

Difficulty: HARD
Tags: Data structures

Implementation
Skill types: Data structures

Starter code:

Solutions:
from math import sqrt, ceil, gcd
from collections import defaultdict

def modInverse(b, m):
	g = gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def sol(n, m, rep):
	r = 1
	for i in range(2, n + 1):
		j = i
		while j % 2 == 0 and rep > 0:
			j //= 2
			rep -= 1
		r *= j
		r %= m
	return r

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	st = []
	ans = 0
	hash = defaultdict(lambda : -1)
	for i in range(n):
		hash[i] = 0
		while st != [] and l[st[-1]] < l[i]:
			z = st.pop()
			hash[i] = max(hash[i], hash[z] + 1)
		if st == []:
			hash[i] = -1
		st.append(i)
		ans = max(ans, hash[i] + 1)
	print(ans)
solve()


(n, t) = (int(input()), list(map(int, input().split())))
(p, s, r) = ([0] * n, [0] * n, t[0])
for i in range(n - 1):
	j = i + 1
	x = t[j]
	if x > r:
		r = x
	else:
		while t[i] < x:
			(s[j], i) = (max(s[j], s[i]), p[i])
		p[j] = i
		s[j] += 1
print(max(s))


n = int(input())
A = list(map(int, input().strip().split()))[::-1]
p = 0
p_max = 0
X = []
for i in A:
	while len(X) > 0 and X[-1][0] < i:
		p = max((p + 1, X[-1][1]))
		X.pop()
	X.append((i, p))
	if p > p_max:
		p_max = p
	p = 0
print(p_max)


N = int(input())
psychos = list(map(int, input().split(' ')))
time_of_death = [0 for i in range(N)]
stack = [(psychos[0], 0)]
for (index, p) in enumerate(psychos):
	if index == 0:
		continue
	if p < stack[-1][0]:
		stack.append((p, 1))
		time_of_death[index] = 1
	elif p > stack[-1][0]:
		max_time = -1
		while stack != [] and p > stack[-1][0]:
			max_time = max(max_time, stack[-1][1])
			del stack[-1]
		if stack == []:
			stack.append((p, 0))
			time_of_death[index] = 0
		else:
			stack.append((p, max_time + 1))
			time_of_death[index] = max_time + 1
print(max(time_of_death))


def main():
	from bisect import bisect_left as bl, bisect_right as br, insort
	import sys, math
	from collections import defaultdict as dd, deque

	def data():
		return sys.stdin.readline().strip()

	def mdata():
		return list(map(int, data().split()))
	out = sys.stdout.write
	INF = float('INF')
	mod = int(1000000000.0) + 7
	n = int(data())
	l = mdata()
	cnt = 0
	m = 0
	max1 = 0
	X = []
	for i in l[::-1]:
		while len(X) and X[-1][0] < i:
			m = max(m + 1, X[-1][1])
			X.pop()
		X.append([i, m])
		if m > max1:
			max1 = m
		m = 0
	print(max1)
main()


n = int(input())
ans = 0
stk = []
for v in map(int, input().split()):
	last = 0
	while len(stk) and stk[-1][0] < v and stk[-1][1]:
		last = max(last, stk[-1][1])
		del stk[-1]
	if not len(stk) or stk[-1][0] < v:
		stk.append((v, 0))
	else:
		stk.append((v, last + 1))
		ans = max(ans, last + 1)
print(ans)


from sys import stdin, stdout

def main(n, a):
	ans = 0
	top = 0
	t = [0 for i in range(n)]
	f = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		tt = 0
		while top > 0 and a[t[top - 1]] < a[i]:
			top -= 1
			tt = max(tt + 1, f[t[top]])
			f[i] = tt
		t[top] = i
		top += 1
	return max(f)
stdout.write('{}\n'.format(main(int(stdin.readline().strip()), list(map(int, input().split(' '))))))


import math
import bisect
import itertools
import sys
I = lambda : sys.stdin.readline()
one = lambda : int(I())
more = lambda : map(int, I().split())
linput = lambda : list(more())
mod = 10 ** 9 + 7

def merge(a, b):
	i = 0
	j = 0
	c = 0
	ans = []
	while i < len(a) and j < len(b):
		if a[i] < b[j]:
			ans.append(a[i])
			i += 1
		else:
			ans.append(b[j])
			c += len(a) - i
			j += 1
	ans += a[i:]
	ans += b[j:]
	return (ans, c)

def mergesort(a):
	if len(a) == 1:
		return (a, 0)
	mid = len(a) // 2
	(left, left_inversion) = mergesort(a[:mid])
	(right, right_inversion) = mergesort(a[mid:])
	(m, c) = merge(left, right)
	c += left_inversion + right_inversion
	return (m, c)

def is_prime(num):
	if num == 1:
		return False
	if num == 2:
		return True
	if num == 3:
		return True
	if num % 2 == 0:
		return False
	if num % 3 == 0:
		return False
	t = 5
	a = 2
	while t <= int(math.sqrt(num)):
		if num % t == 0:
			return False
		t += a
		a = 6 - a
	return True

def ceil(a, b):
	return (a + b - 1) // b
n = one()
a = linput()
st = []
ans = 0
for i in range(n):
	cur = 0
	while st and st[-1][0] < a[-i - 1]:
		cur += 1
		cur = max(cur, st[-1][1])
		st.pop()
	st.append([a[-i - 1], cur])
	ans = max(cur, ans)
print(ans)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353
from sys import stdin
input = stdin.readline

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass
from sys import stdin
input = stdin.readline
n = int(input())
ans = 0
stk = []
for v in map(int, input().split()):
	last = 0
	while len(stk) and stk[-1][0] < v and stk[-1][1]:
		last = max(last, stk[-1][1])
		del stk[-1]
	if not len(stk) or stk[-1][0] < v:
		stk.append((v, 0))
	else:
		stk.append((v, last + 1))
		ans = max(ans, last + 1)
print(ans)
endtime = time.time()


n = int(input())
A = [int(i) for i in input().split()]
ans = 0
st = [0]
tdeath = [-1 for i in range(n)]
for i in range(1, n):
	tdeath[i] = 0
	while len(st) > 0 and A[st[-1]] < A[i]:
		tdeath[i] = max(tdeath[i], tdeath[st[-1]] + 1)
		st.pop()
	if len(st) == 0:
		tdeath[i] = -1
	st.append(i)
	ans = max(ans, tdeath[i] + 1)
print(ans)


n = int(input())
aa = list(map(int, input().split()))
live = []
ans = 0
for i in range(n - 1, -1, -1):
	c = 0
	while len(live) != 0 and live[-1][0] < aa[i]:
		c = max(c + 1, live[-1][1])
		live.pop()
	if c > ans:
		ans = c
	live.append((aa[i], c))
print(ans)