Robot Doc is located in the hall, with n computers stand in a line, numbered from left to right from 1 to n. Each computer contains exactly one piece of information, each of which Doc wants to get eventually. The computers are equipped with a security system, so to crack the i-th of them, the robot needs to collect at least a_{i} any pieces of information from the other computers. Doc can hack the computer only if he is right next to it.

The robot is assembled using modern technologies and can move along the line of computers in either of the two possible directions, but the change of direction requires a large amount of resources from Doc. Tell the minimum number of changes of direction, which the robot will have to make to collect all n parts of information if initially it is next to computer with number 1.

It is guaranteed that there exists at least one sequence of the robot's actions, which leads to the collection of all information. Initially Doc doesn't have any pieces of information.


-----Input-----

The first line contains number n (1 ≤ n ≤ 1000). The second line contains n non-negative integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} < n), separated by a space. It is guaranteed that there exists a way for robot to collect all pieces of the information.


-----Output-----

Print a single number — the minimum number of changes in direction that the robot will have to make in order to collect all n parts of information.


-----Examples-----
Input
3
0 2 0

Output
1

Input
5
4 2 3 0 1

Output
3

Input
7
0 3 1 0 5 2 6

Output
2



-----Note-----

In the first sample you can assemble all the pieces of information in the optimal manner by assembling first the piece of information in the first computer, then in the third one, then change direction and move to the second one, and then, having 2 pieces of information, collect the last piece.

In the second sample to collect all the pieces of information in the optimal manner, Doc can go to the fourth computer and get the piece of information, then go to the fifth computer with one piece and get another one, then go to the second computer in the same manner, then to the third one and finally, to the first one. Changes of direction will take place before moving from the fifth to the second computer, then from the second to the third computer, then from the third to the first computer.

In the third sample the optimal order of collecting parts from computers can look like that: 1->3->4->6->2->5->7.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
info = 0
i = 0
dir = 1
result = 0
while True:
    if info >= a[i]:
        info += 1
        a[i] = n + 1
    if info == n:
        break
    i += dir
    if i < 0 or i == n:
        dir = -dir
        i += dir
        result += 1
print(result)


n = int(input())
a = list(map(int, input().split()))
k = 0
ans = 0
while k != n:
    if ans % 2 == 0:
        for i in range(n):
            if a[i] <= k:
                k += 1
                a[i] = 10000
    else:
        for i in range(n - 1, -1, -1):
            if a[i] <= k:
                k += 1
                a[i] = 10000
    ans += 1
print(ans - 1)


n = int(input())

l = input().split()
l = [int(i) for i in l]

hacked = []

turns = -1

while len(hacked) < n:
    new = []
    for i in range(len(l)):
        if l[i] <= len(hacked):
            new = [i] + new
            hacked.append(i)
    for i in new:
        l.pop(i)
    l.reverse()
    turns += 1

print(turns)


import sys


#sys.stdin = open("input.txt")
#sys.stdout = open("output.txt", "w")

n = int(input())
lst = [int(i) for i in input().split()]
was = [False for i in range(n)]
cur = 0
ind = 0
ans = 0
curdir = 1
while cur < n:
	#print("ind = ", ind)
	if not was[ind]:
		if lst[ind] <= cur:
			cur += 1
			was[ind] = True
			if cur == n:
				break
	if ind == n - 1 and curdir > 0 or ind == 0 and curdir < 0:
		curdir = -curdir
		ans += 1
	ind += curdir

print(ans)



n = int(input())
lst = [int(x) for x in input().split()]

power = 0
answer = 0
while power != len(lst):
	for i in range(len(lst)):
		if lst[i] <= power:
			power += 1
			lst[i] = float('inf')
	
	if power == len(lst):
		break
	answer += 1
	
	for i in range(len(lst)-1, -1, -1):
		if lst[i] <= power:
			power += 1
			lst[i] = float('inf')
	
	if power == len(lst):
		break
	answer += 1

print(answer)

n=int(input())
comp=list(map(int,input().split(' ')))
done=0
checked=[]
c=0
t=-1
d=-1
while done<n:
    t+=1
    d*=-1
    if 0 not in checked:
        if comp[0]==0:
            done+=1
            checked.append(0)
    c+=d
    while c>=0 and c<n:
        if c not in checked:
            if comp[c]<=done:
                done+=1
                checked.append(c)
        c+=d
print(t)

n = int(input())
a = list(map(int, input().split()))
used = [False] * n
flag = True
cur = 0
ans = 0
i = 0
while cur < n:
    ans += 1
    if (i == 0):
        for i in range(n):
            if (not used[i]) and (a[i] <= cur):
                cur += 1
                used[i] = True
    else:
        for i in range(n - 1, -1, -1):
            if (not used[i]) and (a[i] <= cur):
                cur += 1
                used[i] = True
print(ans - 1)
    


n=int(input())
l=list(map(int,input().split()))
f=[0]*n
k=0
ans=0
while k<n:
  for i in range(n):
    if f[i]==0 and l[i]<=k: k+=1; f[i]=1
  if k==n: break
  ans+=1
  for i in range(n):
      if f[n-i-1]==0 and l[n-i-1]<=k: k+=1; f[n-i-1]=1
  if k==n: break
  ans+=1
print(ans)

n = int(input())
a = list(map(int, input().split(' ')[:n]))
n_infos = 0
direction = 1
res = 0

while True:
    if direction == 1:
        r = list(range(n))
    else:
        r = list(range(n-1, -1, -1))

    for i in r:
        if n_infos >= a[i]:
            a[i] = float("inf")
            n_infos += 1

    if n_infos == n:
        break

    direction = -direction
    res += 1
print(res)


n = int(input())
a = [int(x) for x in input().split()]
k = 0
pov = 0
used = [False] * n
for i in range(n):
    for j in range(n):
        if used[j] == False and a[j] <= k:
            used[j] = True
            k += 1
    r = 0
    for j in range(n):
        if used[j] == False:
            r = 1
    if r == 0:
        print(pov)
        break
    else:
        pov += 1
    for j in range(n - 1, -1, -1):
        if used[j] == False and a[j] <= k:
            used[j] = True
            k += 1
    r = 0
    for j in range(n):
        if used[j] == False:
            r = 1
    if r == 0:
        print(pov)
        break
    else:
        pov += 1

3

import itertools as ittls
from collections import Counter

from pprint import pprint as pprint

import re
import math


def sqr(x):
    return x*x

def inputarray(func=int):
    return list(map(func, input().split()))

# --------------------------------------
# --------------------------------------

N = int(input())
A = list(inputarray())

power, i = 0, 0
mask = [0]*N

while power < N:
    s = 0

    domain = list(range(N)) if i&1 != 1\
            else list(range(N - 1, -1, -1))
    for j in domain:
        if mask[j] == 0 and A[j] <= power:
            mask[j] = 1
            power = power + 1

    i = i + 1

print(i - 1)


import sys
lines = iter(sys.stdin.read().split("\n"))
n = int(next(lines))
nums = list(map(int, next(lines).strip(" ").split(" ")))
total = 0
count = 0
turns = -1
direction = 1
def traverse(nums, direction, total, count):
    """direction - 0: left to right, 1: right to left"""
    if direction == 0:
        for i, num in enumerate(nums):
            if num != -1 and num <= total:
                count += 1
                total += 1
                nums[i] = -1
    elif direction == 1:
        for i in range(len(nums) - 1, -1, -1):
            num = nums[i]
            if num != -1 and num <= total:
                count += 1
                total += 1
                nums[i] = -1
    return total, count
while count < n:
    turns += 1
    direction = 1 - direction
    total, count = traverse(nums, direction, total, count)
print(turns)


n=int(input())
a=list(map(int,input().split()))
s=0
r=0
i=0
k=1
f=0
while s!=n:
	if a[i]<=s:
		s+=1
		a[i]=9999
	if (s!=n)and((i==n-1)or((i==0)and(f))):
		r+=1
		k*=-1
		f=1
	i+=k
print(r)


n = int(input())
a = [int(x) for x in input().split()]

k = 0
t = -1

while a:
    t += 1

    next_a = []
    for elem in a:
        if elem <= k:
            k += 1
        else:
            next_a.append(elem)

    next_a.reverse()
    a = next_a

print(t)

n = int(input())
L = list(map(int, input().split()))
P = [ 0 for _ in range(n)]
r = 0
t = 0
while t < n:
    for k in range(n):
        if P[k] == 0 and L[k] <= t:
            t+=1
            P[k] = 1
    r+=1
    if t == n:
        break
    for k in range(n):
        if P[n-k-1] == 0 and L[n-k-1] <= t:
            t+=1
            P[n-k-1] = 1
    r+=1
print(r-1)

n = int(input())
a = list(map(int, input().split()))
#a = [4, 2, 3, 0, 1]
used = [False for i in range(n)]
k = 0

for i in range(n):
    flag = False
    for j in range(n):
        if a[j] <= k and used[j] == False:
            used[j] = True
            k += 1
    for j in range(n):
        if used[j] == False:
            flag = True
    if flag == False:
        print(2 * i)
        break
    for j in range(n - 1, -1, -1):
        if a[j] <= k and used[j] == False:
            used[j] = True
            k += 1  
    flag = False
    for j in range(n):
        if used[j] == False:
            flag = True
    if flag == False:
        print(2 * i + 1)
        break    


_ = input()
ns = map(int, input().split())
c = 0
cur = 0
while True:
    new = []
    for i in ns:
        if i <= cur:
            cur += 1
        else:
            new.append(i)
    if not new:
        break
    ns = reversed(new)
    c += 1
print(c)

n = int(input())
a = list(map(int,input().split()))
q = 0
c = 0
while len(a) > 0:
    de = set()
    for i in range(len(a)):
        if a[i] <= q:
            q += 1
            de.add(i)
    c += 1
    a = [a[i] for i in reversed(range(len(a))) if i not in de]
print(c-1)

n = int(input())
l = list(map(int, input().split()))
nl = [-1]*n
keys = 0
turns = 0
#print(l)
#print("BEGIN-----------------")
while l != nl:
    if turns % 2 == 0:
        for pos in range(n):
            if l[pos] <= keys and l[pos] != -1:
                keys += 1
                l[pos] = -1
    else:
        for pos in range(n-1, -1, -1):
            if l[pos] <= keys and l[pos] != -1:
                keys += 1
                l[pos] = -1
    #print(l)
    turns += 1
print(turns-1)


n = int(input())
lst = list(map(int, input().split()))
ans = 0
zap = 0
used = [False] * (n)
while zap != n:
    if zap != 0:
        ans += 1
    for i in range(n):
        if not used[i] and zap >= lst[i]:
            used[i] = True
            zap += 1
      
    if zap == n:
        break
    ans += 1
    for i in range(n - 1, -1, -1):
        if not used[i] and zap >= lst[i]:
            used[i] = True
            zap += 1

print(ans)    


#!/usr/bin/env python

from sys import stdin

n = int(stdin.readline())
a = [int(x) for x in stdin.readline().split()]
visited = [False] * n
visited_count = 0
turns = 0

dir = 1
position = 0

while True:
    if not visited[position] and a[position] <= visited_count:
        visited[position] = True
        visited_count += 1
    if visited_count == n:
        break
    if dir == 1 and position == n-1 or dir == -1 and position == 0:
        dir = -dir
        turns += 1
    position += dir

print(turns)


#!/usr/bin/env python
# -*- coding: utf-8 -*-

n = int(input())
C = list(map(int,input().split()))

def check(init):
    d = init
    done = [False for i in range(n)]
    cracked = 0
    changed = 0
    while cracked < n:
        if d == 0:
            for i in range(n):
                if not done[i] and C[i] <= cracked:
                    done[i] = True
                    cracked += 1
        else:
            for i in range(n)[::-1]:
                if not done[i] and C[i] <= cracked:
                    done[i] = True
                    cracked += 1
        d = d ^ 1
        if cracked < n:
            changed += 1
    return changed

print(check(0))


def main():
    n = int(input())
    arr = [int(x) for x in input().split()]
    used = [False] * n
    napr = True
    c = 0
    ans = 0
    while False in used:
        if napr:
            for i in range(n):
                if c >= arr[i] and used[i] == False:
                    used[i] = True
                    c += 1
        else:
            for i in range(n-1, 0-1, -1):
                if c >= arr[i] and used[i] == False:                
                    used[i] = True
                    c += 1    
        napr = not(napr)
        if False in used:
            ans += 1
             
    print(ans)
        
main()

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import time

n   = int(input())
A   = [int(i) for i in input().split()]

start = time.time()

t   = 0
now = 0
ans = -1

while(t < n):
    ans += 1
    for i in range(n):
        if A[i] >= 0 and A[i] <= t:
            t    += 1
            A[i] = -1
    if (t == n):
        break
    ans += 1
    for i in range(n):
        if A[n-1-i]>= 0 and A[n-1-i] <= t:
            t        += 1
            A[n-1-i] = -1

print(ans)
finish = time.time()
#print(finish - start)


def getNum(n, arr):
    st1 = []
    st2 = []
    worth = 0
    count = 0
    
    for i in range(n):
        if arr[i] <= worth:
            worth += 1
        else:
            st1.append(arr[i])
    
    if len(st1) == 0:
        return count
    
    count += 1
    while len(st1) != 0:
        if st1[-1] <= worth:
            st1.pop()
            worth += 1
        else:
            st2.append(st1.pop())
        
        if len(st1) == 0:
            if len(st2) == 0:
                return count
            
            st1 = st2
            st2 = []
            count += 1
    
    return count
    
    
n = int(input())

arr = list(map(int, input().split()))

print(getNum(n, arr))