package main

import (
	"bufio"
	"os"
	"strconv"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	buf := make([]byte, 0, 1024*1024)
	scanner.Buffer(buf, 10*1024*1024)

	if !scanner.Scan() {
		return
	}
	n, _ := strconv.Atoi(scanner.Text())

	a := make([]int, n+1)
	pos := make([][]int, n+1)
	for i := 1; i <= n; i++ {
		scanner.Scan()
		a[i], _ = strconv.Atoi(scanner.Text())
		pos[a[i]] = append(pos[a[i]], i)
	}

	treeMax := make([]int, 4*(n+2))
	treeMin := make([]int, 4*(n+2))
	lazy := make([]int, 4*(n+2))

	var build func(node, l, r int)
	build = func(node, l, r int) {
		if l == r {
			treeMax[node] = l
			treeMin[node] = l
			return
		}
		mid := (l + r) / 2
		build(node*2, l, mid)
		build(node*2+1, mid+1, r)
		treeMax[node] = getMax(treeMax[node*2], treeMax[node*2+1])
		treeMin[node] = getMin(treeMin[node*2], treeMin[node*2+1])
	}

	var pushDown func(node int)
	pushDown = func(node int) {
		if lazy[node] != 0 {
			lz := lazy[node]
			lazy[node*2] += lz
			treeMax[node*2] += lz
			treeMin[node*2] += lz

			lazy[node*2+1] += lz
			treeMax[node*2+1] += lz
			treeMin[node*2+1] += lz

			lazy[node] = 0
		}
	}

	var update func(node, l, r, ql, qr, val int)
	update = func(node, l, r, ql, qr, val int) {
		if ql <= l && r <= qr {
			treeMax[node] += val
			treeMin[node] += val
			lazy[node] += val
			return
		}
		pushDown(node)
		mid := (l + r) / 2
		if ql <= mid {
			update(node*2, l, mid, ql, qr, val)
		}
		if qr > mid {
			update(node*2+1, mid+1, r, ql, qr, val)
		}
		treeMax[node] = getMax(treeMax[node*2], treeMax[node*2+1])
		treeMin[node] = getMin(treeMin[node*2], treeMin[node*2+1])
	}

	var queryMax func(node, l, r, ql, qr int) int
	queryMax = func(node, l, r, ql, qr int) int {
		if ql <= l && r <= qr {
			return treeMax[node]
		}
		pushDown(node)
		mid := (l + r) / 2
		res := -1000000000
		if ql <= mid {
			res = getMax(res, queryMax(node*2, l, mid, ql, qr))
		}
		if qr > mid {
			res = getMax(res, queryMax(node*2+1, mid+1, r, ql, qr))
		}
		return res
	}

	var queryMin func(node, l, r, ql, qr int) int
	queryMin = func(node, l, r, ql, qr int) int {
		if ql <= l && r <= qr {
			return treeMin[node]
		}
		pushDown(node)
		mid := (l + r) / 2
		res := 1000000000
		if ql <= mid {
			res = getMin(res, queryMin(node*2, l, mid, ql, qr))
		}
		if qr > mid {
			res = getMin(res, queryMin(node*2+1, mid+1, r, ql, qr))
		}
		return res
	}

	build(1, 0, n)
	ans := make([]int, n+1)

	for v := 1; v <= n; v++ {
		if len(pos[v]) == 0 {
			continue
		}
		for _, i := range pos[v] {
			mPos := queryMax(1, 0, n, i, n) - queryMin(1, 0, n, 0, i-1)
			ans[i] = getMax(ans[i], mPos/2)
		}
		for _, i := range pos[v] {
			update(1, 0, n, i, n, -2)
		}
		for _, i := range pos[v] {
			mNeg := queryMax(1, 0, n, 0, i-1) - queryMin(1, 0, n, i, n)
			ans[i] = getMax(ans[i], (mNeg-1)/2)
		}
	}

	out := bufio.NewWriter(os.Stdout)
	for i := 1; i <= n; i++ {
		if i > 1 {
			out.WriteString(" ")
		}
		out.WriteString(strconv.Itoa(ans[i]))
	}
	out.WriteString("\n")
	out.Flush()
}

func getMax(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func getMin(a, b int) int {
	if a < b {
		return a
	}
	return b
}