package main

import (
	"bufio"
	"fmt"
	"os"
)

type SegTree struct {
	maxVal []int
	minVal []int
	lazy   []int
	size   int
}

func NewSegTree(n int, initVals []int) *SegTree {
	size := 1
	for size <= n {
		size *= 2
	}
	st := &SegTree{
		maxVal: make([]int, 2*size),
		minVal: make([]int, 2*size),
		lazy:   make([]int, 2*size),
		size:   size,
	}
	st.build(1, 0, size-1, initVals)
	return st
}

func (st *SegTree) build(node, l, r int, initVals []int) {
	if l == r {
		if l < len(initVals) {
			st.maxVal[node] = initVals[l]
			st.minVal[node] = initVals[l]
		}
		return
	}
	mid := (l + r) / 2
	st.build(node*2, l, mid, initVals)
	st.build(node*2+1, mid+1, r, initVals)
	st.maxVal[node] = max(st.maxVal[node*2], st.maxVal[node*2+1])
	st.minVal[node] = min(st.minVal[node*2], st.minVal[node*2+1])
}

func (st *SegTree) push(node int) {
	if st.lazy[node] != 0 {
		lz := st.lazy[node]
		st.maxVal[node*2] += lz
		st.minVal[node*2] += lz
		st.lazy[node*2] += lz
		st.maxVal[node*2+1] += lz
		st.minVal[node*2+1] += lz
		st.lazy[node*2+1] += lz
		st.lazy[node] = 0
	}
}

func (st *SegTree) Update(ql, qr, val int) {
	st.update(1, 0, st.size-1, ql, qr, val)
}

func (st *SegTree) update(node, l, r, ql, qr, val int) {
	if ql <= l && r <= qr {
		st.maxVal[node] += val
		st.minVal[node] += val
		st.lazy[node] += val
		return
	}
	st.push(node)
	mid := (l + r) / 2
	if ql <= mid {
		st.update(node*2, l, mid, ql, qr, val)
	}
	if qr > mid {
		st.update(node*2+1, mid+1, r, ql, qr, val)
	}
	st.maxVal[node] = max(st.maxVal[node*2], st.maxVal[node*2+1])
	st.minVal[node] = min(st.minVal[node*2], st.minVal[node*2+1])
}

func (st *SegTree) QueryMax(ql, qr int) int {
	return st.queryMax(1, 0, st.size-1, ql, qr)
}

func (st *SegTree) queryMax(node, l, r, ql, qr int) int {
	if ql <= l && r <= qr {
		return st.maxVal[node]
	}
	st.push(node)
	mid := (l + r) / 2
	res := -int(1e9)
	if ql <= mid {
		res = max(res, st.queryMax(node*2, l, mid, ql, qr))
	}
	if qr > mid {
		res = max(res, st.queryMax(node*2+1, mid+1, r, ql, qr))
	}
	return res
}

func (st *SegTree) QueryMin(ql, qr int) int {
	return st.queryMin(1, 0, st.size-1, ql, qr)
}

func (st *SegTree) queryMin(node, l, r, ql, qr int) int {
	if ql <= l && r <= qr {
		return st.minVal[node]
	}
	st.push(node)
	mid := (l + r) / 2
	res := int(1e9)
	if ql <= mid {
		res = min(res, st.queryMin(node*2, l, mid, ql, qr))
	}
	if qr > mid {
		res = min(res, st.queryMin(node*2+1, mid+1, r, ql, qr))
	}
	return res
}

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

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

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n int
	fmt.Fscan(reader, &n)

	a := make([]int, n+1)
	pos := make([][]int, n+1)
	for i := 1; i <= n; i++ {
		fmt.Fscan(reader, &a[i])
		pos[a[i]] = append(pos[a[i]], i)
	}

	initVals := make([]int, n+1)
	for i := 0; i <= n; i++ {
		initVals[i] = -i
	}

	st := NewSegTree(n+1, initVals)
	ans := make([]int, n+1)

	for x := 1; x <= n; x++ {
		for _, i := range pos[x] {
			maxQ := st.QueryMax(0, i-1)
			minQ := st.QueryMin(i, n)
			v2 := maxQ - minQ
			ans[i] = max(ans[i], v2/2)
		}

		for _, i := range pos[x] {
			st.Update(i, n, 2)
		}

		for _, i := range pos[x] {
			maxP := st.QueryMax(i, n)
			minP := st.QueryMin(0, i-1)
			v1 := maxP - minP
			ans[i] = max(ans[i], (v1-1)/2)
		}
	}

	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()
	for i := 1; i <= n; i++ {
		if i > 1 {
			fmt.Fprint(writer, " ")
		}
		fmt.Fprint(writer, ans[i])
	}
	fmt.Fprintln(writer)
}