There is an infinite sequence consisting of all positive integers in the increasing order: *p* = {1, 2, 3, ...}. We performed *n* swap operations with this sequence. A *swap*(*a*, *b*) is an operation of swapping the elements of the sequence on positions *a* and *b*. Your task is to find the number of inversions in the resulting sequence, i.e. the number of such index pairs (*i*, *j*), that *i* &lt; *j* and *p*<sub class="lower-index">*i*</sub> &gt; *p*<sub class="lower-index">*j*</sub>.
The first line contains a single integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>) — the number of swap operations applied to the sequence.

Each of the next *n* lines contains two integers *a*<sub class="lower-index">*i*</sub> and *b*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>, *a*<sub class="lower-index">*i*</sub> ≠ *b*<sub class="lower-index">*i*</sub>) — the arguments of the swap operation.
import sys
input = sys.stdin.readline

n = int(input())
a = [0] + list(map(int, input().split()))

dp = [0] * (n + 1)
dp1 = [0] * (n + 1)
t = [0] * (n + 1)
t1 = [0] * (n + 1)

t[1] = a[1]
for i in range(2, n + 1):
    if a[i] <= t[i - 1]:
        dp[i] = dp[i - 1] + t[i - 1] - a[i] + 1
        t[i] = t[i - 1] + 1
    else:
        t[i] = a[i]
        dp[i] = dp[i - 1]

t1[n] = a[n]
for i in range(n - 1, 0, -1):
    if a[i] <= t1[i + 1]:
        dp1[i] = dp1[i + 1] + t1[i + 1] - a[i] + 1
        t1[i] = t1[i + 1] + 1
    else:
        t1[i] = a[i]
        dp1[i] = dp1[i + 1]

ans = min(dp1[1], dp[n])
for i in range(2, n):
    ans = min(ans, dp1[i] + dp[i] - min(t[i], t1[i]) + a[i])

print(ans)

	  	 	 		 		 		         	 	  		