Problem:


Score : 2400 points

Problem Statement

Takahashi loves sorting.

He has a permutation (p_1,p_2,...,p_N) of the integers from 1 through N. Now, he will repeat the following operation until the permutation becomes (1,2,...,N):

First, we will define high and low elements in the permutation, as follows. The i-th element in the permutation is high if the maximum element between the 1-st and i-th elements, inclusive, is the i-th element itself, and otherwise the i-th element is low.

Then, let a_1,a_2,...,a_k be the values of the high elements, and b_1,b_2,...,b_{N-k} be the values of the low elements in the current permutation, in the order they appear in it.

Lastly, rearrange the permutation into (b_1,b_2,...,b_{N-k},a_1,a_2,...,a_k).

How many operations are necessary until the permutation is sorted?

Constraints

1 ≤ N ≤ 2×10^5

(p_1,p_2,...,p_N) is a permutation of the integers from 1 through N.

Input

Input is given from Standard Input in the following format:

N
p_1 p_2 ... p_N

Output

Print the number of operations that are necessary until the permutation is sorted.

Sample Input 1

5
3 5 1 2 4

Sample Output 1

3

The initial permutation is (3,5,1,2,4), and each operation changes it as follows:

In the first operation, the 1-st and 2-nd elements are high, and the 3-rd, 4-th and 5-th are low. The permutation becomes: (1,2,4,3,5).

In the second operation, the 1-st, 2-nd, 3-rd and 5-th elements are high, and the 4-th is low. The permutation becomes: (3,1,2,4,5).

In the third operation, the 1-st, 4-th and 5-th elements are high, and the 2-nd and 3-rd and 5-th are low. The permutation becomes: (1,2,3,4,5).

Sample Input 2

5
5 4 3 2 1

Sample Output 2

4

Sample Input 3

10
2 10 5 7 3 6 4 9 8 1

Sample Output 3

6



Sample input:
5
3 5 1 2 4


Sample output:
3

Submission status: Wrong Answer

Solution code:

N = int(input())
P = list(map(int,input().split()))
P2 =[0]*(N+1)

for i in range(N):
    P2[P[i]] = i+1

T = 0
f = N
i = N-1
flag = 0

while i >= 0:
    if flag == 0:
        if P2[i] < P2[i+1]:
            f = i
        else:
            T = T+1
            f = f-1
            flag = 1
    else:
        if (P2[i+1]-P2[i])*(P2[i]-P2[f])*(P2[f]-P2[i+1]) > 0:
            T = T+1
            f = i+1
    i = i-1

print(T)

Submission status: Wrong Answer

Solution code:

N = int(input())

p1 = list(map(int,input().split()))
p2 = []

count = 0
flag = 0
flag2 = 1

while flag2 == 1:
    flag = 0
    flag2 = 0
    MAX = 0
    for i in range(N):
        if p1[i] > MAX:
            MAX = p1[i]
            flag = flag + 1
            p2.append(p1[i])
        else:
            L = len(p2)
            p2.insert(L-flag,p1[i])
            if i > 0:
                if p2[L-flag] > p2[L-flag+1]:
                    flag2 = 1
                elif flag < L:
                    if p2[L-flag-1] > p2[L-flag]:
                        flag2 = 1

    p1 = p2[:]
    count = count + 1
    p2.clear()
    
print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
p=list(map(int,input().split()))

count=n-1

while True:
    tmp=p.index(max(p))
    p.remove(max(p))
    if p==[]: break
    if p.index(max(p))<tmp: count-=1

print(count+1)

Submission status: Wrong Answer

Solution code:
from sys import stdin
rr = lambda: stdin.readline().strip()
rrM = lambda: map(int, rr().split())

N = int(rr())
A = rrM()
index = {u:i for i,u in enumerate(A)}
ans = 0
while N:
    if N == 1: break
    ix = index[N]
    for j in xrange(ix, -1, -1):
        if A[j] == N:
            N -= 1
    ans += 1
print ans

Submission status: Wrong Answer

Solution code:
N = int(raw_input())
p = map(int, raw_input().split())
# print(p[:2])

j = 0
while True:
    j += 1
    higher = []
    lower = []
    for i in range(0, N):
        if p[i] == reduce(lambda x, y: max(x, y), p[:i+1], 0):
            higher.append(p[i])
        else:
            lower.append(p[i])
    p = lower + higher
    # print p

    if p == range(1, N+1):
        print(j)
        break

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
nums=list(map(int,input().split()))
count=0

while True:
    min=0
    H=[]
    L=[]
    for num in nums:
        if min<num:
            min=num
            H.append(num)
        else:
            L.append(num)
    if not L:
        break
    nums=L+H
    count+=1
    
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
p = list(map(int, input().split()))

high = []
low = []
counter = 0

while len(high) != N:
    high = []
    low = []
    for i in range(N):
        flag = True
        for j in high:
            if p[i] < j:
                low.append(p[i])
                flag = False
                break

        if flag:
            high.append(p[i])

    p = []
    for i in low:
        p.append(i)
    for i in high:
        p.append(i)
    counter += 1

print(counter-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = list(map(int,input().split()))
clnum = 0
Ans = list(P)
Ans.sort()
while P != Ans:
	A = []
	B = []
	for i in range(N):
		if i == 0:
			A.append(P[0])
			continue

		if (P[i]) >= (max(P[0:i+1:1])):
			A.append(P[i])
		else:
			B.append(P[i])
	P = B + A
	clnum += 1
print(clnum)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
gyou = list(map(int,input().split()))
num = 0
while True:
    high = [str(gyou[0])]
    low = []
    for i in range(1,N):
        if max(gyou[0:i]) < gyou[i]:
            high += [str(gyou[i])]
        else:
            low += [str(gyou[i])]
    if low == []:
        break
    else:
        num += 1
        gyou = list(map(int,low + high))
print(num)

Submission status: Time Limit Exceeded

Solution code:
N = input()
p = map(int, raw_input().split())

def strangesort(arr):
    high = [i for index, i in enumerate(arr) if i >= max(arr[:index + 1])]
    other = [i for index, i in enumerate(arr) if i < max(arr[:index + 1])]
    return other + high


count = 0
while p != range(1, N + 1):
    p = strangesort(p)
    count += 1

print count

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
p = map(int, raw_input().split())

count = 0
while True:
    flagEnd = True
    high = [p[0]]
    low = []

    for i in range(len(p) - 1):
        if p[i+1] < max(p[:i+1]):
            low.append(p[i+1])
            flagEnd = False
        else:
            high.append(p[i+1])

    if flagEnd:
        break

    low.extend(high)
    p = low
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p2 = [ int(i) for i in input().split() ]
ps = sorted(p2)

cnt=0
while True:
    if p2 == ps: break
    cnt += 1
    high = []
    low = []
    for i in range(len(p2)):
        if p2[i] == max(p2[0:i+1]):
            high.append(p2[i])
        else:
            low.append(p2[i])
    p2 = low + high

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = [ int(i) for i in input().split() ]

p2=p[:]
ps = sorted(p)

cnt=0
while True:
    if p2 == ps: break
    cnt += 1
    high = []
    low = []
    for i in range(len(p)):
        if p2[i] == max(p2[0:i+1]):
            high.append(p2[i])
        else:
            low.append(p2[i])
    p2 = low + high

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain


N = int(raw_input())
p = map(int, raw_input().split())
# print(p)

def is_sorted(l):
    for i in xrange(0, len(l)-1):
        if l[i] != i + 1:
            return False
    return True


def is_gt(i, l):
    for e in l:
        if e > i:
            return False
    return True

def shrink(l):
    i = 1
    while i < len(l) and l[-i] == len(l)-(i-1):
        i += 1
    return l[0:-(i-1)]


j = 0
while not is_sorted(p):
    higher = [p[0]]
    lower = []
    for e in p[1:]:
        # if e >= reduce(lambda x, y: max(x, y), higher, 0):
        if is_gt(e, higher):
            higher.append(e)
        else:
            lower.append(e)
    # p = [e for e in chain(lower, higher)]
    lower.extend(higher)
    p = shrink(lower)
    # print p
    j += 1

print(j)

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain


N = int(raw_input())
p = map(int, raw_input().split())
# print(p)

def is_sorted(l):
    for i in xrange(0, len(l)-1):
        if l[i] != i + 1:
            return False
    return True


def is_gt(i, l):
    for e in l:
        if e > i:
            return False
    return True

def shrink(l):
    while len(l) > 1 and l[len(l)-1] == len(l):
        l.pop()
    return l


j = 0
while not is_sorted(p):
    higher = [p[0]]
    lower = []
    for e in p[1:]:
        # if e >= reduce(lambda x, y: max(x, y), higher, 0):
        if is_gt(e, higher):
            higher.append(e)
        else:
            lower.append(e)
    # p = [e for e in chain(lower, higher)]
    p = lower.extend(higher)
    p = lower
    shrink(p)
    # print p
    j += 1

print(j)

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain


N = int(raw_input())
p = map(int, raw_input().split())
# print(p)

def is_sorted(l):
    for i in xrange(0, len(l)-1):
        if l[i] != i + 1:
            return False
    return True


def is_gt(i, l):
    for e in l:
        if e > i:
            return False
    return True

def shrink(l):
    while len(l) > 1 and l[len(l)-1] == len(l):
        l.pop()
    return l


j = 0
while not is_sorted(p):
    higher = [p[0]]
    lower = []
    for e in p[1:]:
        # if e >= reduce(lambda x, y: max(x, y), higher, 0):
        if is_gt(e, higher):
            higher.append(e)
        else:
            lower.append(e)
    # p = [e for e in chain(lower, higher)]
    # p = lower
    p = lower + higher
    shrink(p)
    # print p
    j += 1

print(j)

Submission status: Time Limit Exceeded

Solution code:
n=input()
l=map(int,raw_input().split())
max=l[0]
def check(l,n):
    a=[]
    b=[]
    max=l[0]
    for i in range(n):
        if l[i]>=max:
            a.append(l[i])
            max=l[i]
        else:
            b.append(l[i])
    lnew=b+a
    return lnew
llast=[i for i in range(1,n+1)]
z=0
while l!=llast:
    l=check(l,n)
    z+=1
print z

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain


N = int(raw_input())
p = map(int, raw_input().split())
# print(p)

def is_sorted(l):
    for i in range(0, len(l)-1):
        if l[i] != i + 1:
            return False
    return True


j = 0
while not is_sorted(p):
    # j += 1
    # higher = []
    higher = [p[0]]
    lower = []
    for i in range(1, N):
        if p[i] >= reduce(lambda x, y: max(x, y), higher, 0):
            higher.append(p[i])
        else:
            lower.append(p[i])
    p = [e for e in chain(lower, higher)]
    # p = lower + higher
    # print p
    j += 1

print(j)

Submission status: Time Limit Exceeded

Solution code:
N=int(raw_input())
p=map(int,raw_input().split())
a=[i+1 for i in range(N)]

cnt=0
while p!=a:
	l=[];h=[]
	for i in range(N):
		if p[i]==max(p[:i+1]): h.append(p[i])
		else: l.append(p[i])
	p=l+h
	cnt+=1
print cnt

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain

N = int(raw_input())
p = map(int, raw_input().split())
# print(p[:2])

def is_sorted(l):
    for i in range(0, len(l)-1):
        if l[i] != i + 1:
            return False
    return True


if is_sorted(p):
    print(0)
else:
    j = 0
    while True:
        j += 1
        higher = []
        lower = []
        for i in range(0, N):
            if p[i] == reduce(lambda x, y: max(x, y), p[:i+1], 0):
                higher.append(p[i])
            else:
                lower.append(p[i])
        p = [e for e in chain(lower, higher)]
        # p = lower + higher
        # print p

        if is_sorted(p):
            print(j)
            break

Submission status: Time Limit Exceeded

Solution code:
N=int(raw_input())
p=map(int,raw_input().split())
a=[i+1 for i in range(N)]

cnt=0
while p!=a:
	d=[0]*N
	hterm=[];lterm=[]
	for i in range(N):
		d[i]=p[i]
		if p[i]==max(d): hterm.append(i)
		else: lterm.append(i)
	p=[]
	for i in lterm+hterm:
		p.append(d[i])
	cnt+=1
print cnt

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))
a=[]
b=[]

count=0
while True:
    max=0
    for i in range(n):
        if p[i]>=max: a.append(p[i]); max=p[i]
        else: b.append(p[i])
    if b+a==p: break
    else: p,a,b=b+a,[],[]
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))
a=[]
b=[]

count=0
while p != sorted(p):
    max=0
    for i in range(n):
        if p[i]>=max: a.append(p[i]); max=p[i]
        else: b.append(p[i])
    p,a,b=b+a,[],[]
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))
a=[]
b=[]

count=0
while True:
    if p==sorted(p): break
    for i in range(n):
        if p[i]==max(p[0:i+1]): a.append(p[i])
        else: b.append(p[i])
    p,a,b=b+a,[],[]
    count+=1

print(count)

Submission status: Accepted

Solution code:
N,*P=map(int,open(0).read().split());I={P[i]:i+1for i in range(N)};I[0]=T=f=0
while N>1:
 x=I[f];y=I[N-1];z=I[N]
 if(z>y)^(y>x)^(x>z):T+=1;f=N
 N-=1
print(T)

Submission status: Accepted

Solution code:
N = int(input())
P = list(map(int, input().split()))

Pi = [0] * (N + 1)
for i, n in enumerate(P, 1):
    Pi[n] = i

i = N - 1
T = 0
f = 0

while i:
    i_f = Pi[f]
    i_i = Pi[i]
    i_ii = Pi[i + 1]
    if i_f < i_ii < i_i or i_i < i_f < i_ii or i_ii < i_i < i_f:
        T += 1
        f = i + 1
    i -= 1

print(T)

Submission status: Accepted

Solution code:
N = int(input())
P = list(map(int, input().split()))

if N == 1:
    print(0)
    exit()

Pi = [0] * (N + 1)
for i, n in enumerate(P, 1):
    Pi[n] = i

T = [0] * N
f = [0] * N

if Pi[N] > Pi[N - 1]:
    T[N - 1] = 0
    f[N - 1] = N - 1
else:
    T[N - 1] = 1
    f[N - 1] = N

for i in range(N - 2, 0, -1):
    if T[i + 1] == 0:
        i_i = Pi[i]
        i_ii = Pi[i + 1]
        if i_ii > i_i:
            T[i] = T[i + 1]
            f[i] = f[i + 1]
        else:
            T[i] = T[i + 1] + 1
            f[i] = i + 1
    else:
        i_f = Pi[f[i + 1]]
        i_i = Pi[i]
        i_ii = Pi[i + 1]
        if i_f < i_i < i_ii or i_ii < i_f < i_i or i_i < i_ii < i_f:
            T[i] = T[i + 1]
            f[i] = f[i + 1]
        else:
            T[i] = T[i + 1] + 1
            f[i] = i + 1

print(T[1])

Submission status: Accepted

Solution code:

N = int(input())
P = list(map(int,input().split()))
P2 =[0]*(N+1)

i = N-1
T = 0

for j in range(N):
    P2[P[j]] = j+1

while i >= 0:
    if P2[i] > P2[i+1]:
        T = 1
        f = i+1
        i = i-1
        break
    i = i-1
    

while i > 0:
    if (P2[i+1]-P2[i])*(P2[i]-P2[f])*(P2[f]-P2[i+1]) > 0:
        T = T+1
        f = i+1
    i = i-1

print(T)

Submission status: Runtime Error

Solution code:
N = int(input())
P = list(map(int, input().split()))

Pi = [0] * (N + 1)
for i, n in enumerate(P, 1):
    Pi[n] = i

T = [0] * N
f = [0] * N

if Pi[N] > Pi[N - 1]:
    T[N - 1] = 0
    f[N - 1] = N - 1
else:
    T[N - 1] = 1
    f[N - 1] = N

for i in range(N - 2, 0, -1):
    if T[i + 1] == 0:
        i_i = Pi[i]
        i_ii = Pi[i + 1]
        if i_ii > i_i:
            T[i] = T[i + 1]
            f[i] = f[i + 1]
        else:
            T[i] = T[i + 1] + 1
            f[i] = i + 1
    else:
        i_f = Pi[f[i + 1]]
        i_i = Pi[i]
        i_ii = Pi[i + 1]
        if i_f < i_i < i_ii or i_ii < i_f < i_i or i_i < i_ii < i_f:
            T[i] = T[i + 1]
            f[i] = f[i + 1]
        else:
            T[i] = T[i + 1] + 1
            f[i] = i + 1

print(T[1])

Submission status: Runtime Error

Solution code:
N = int(raw_input())
p = map(int, raw_input().split())

count = 0
while True:
    flagEnd = True
    high = [p[0]]
    low = []

    for i in range(len(p) - 1):
        if p[i+1] < p[i]:
            low.append(p[i+1])
            flagEnd = False
        else:
            high.append(p[i+1])

    if flagEnd:
        break

    p = low.extend(high)
    count += 1

print(count)