```go
package main

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

// Scanner setup for fast I/O
var scanner *bufio.Scanner

func init() {
	scanner = bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1024*1024), 64*1024*1024)
}

func readInt() int {
	scanner.Scan()
	s := scanner.Bytes()
	x := 0
	for _, b := range s {
		x = x*10 + int(b-'0')
	}
	return x
}

type BIT struct {
	tree []int
	n    int
}

func NewBIT(n int) *BIT {
	return &BIT{make([]int, n+1), n}
}

func (b *BIT) Add(i, delta int) {
	for i <= b.n {
		b.tree[i] += delta
		i += i & -i
	}
}

func (b *BIT) Query(i int) int {
	sum := 0
	for i > 0 {
		sum += b.tree[i]
		i -= i & -i
	}
	return sum
}

func (b *BIT) QueryRange(l, r int) int {
	if l > r {
		return 0
	}
	return b.Query(r) - b.Query(l-1)
}

type Element struct {
	idx int
	val int
}

type Query struct {
	k   int
	val int
}

func main() {
	if !scanner.Scan() {
		return
	}
	// Parse n
	nBytes := scanner.Bytes()
	n := 0
	for _, b := range nBytes {
		n = n*10 + int(b-'0')
	}

	if n == 0 {
		fmt.Println(0)
		return
	}

	s := make([]int, n)
	for i := 0; i < n; i++ {
		s[i] = readInt()
	}

	// Precompute prefix max and suffix min
	prefMax := make([]int, n)
	curMax := -1
	for i := 0; i < n; i++ {
		if s[i] > curMax {
			curMax = s[i]
		}
		prefMax[i] = curMax
	}

	suffMin := make([]int, n)
	curMin := 2147483647
	for i := n - 1; i >= 0; i-- {
		if s[i] < curMin {
			curMin = s[i]
		}
		suffMin[i] = curMin
	}

	// Initial minCost with full sort P(n) -> n^2
	minCost := int64(n) * int64(n)

	// Part 1: Gap Case (Non-overlapping)
	// We look for a sorted middle segment s[l...r] such that prefix and suffix fix the rest.
	validR := make([]bool, n)
	for r := 0; r < n; r++ {
		if r == n-1 || s[r] <= suffMin[r+1] {
			validR[r] = true
		}
	}

	i := 0
	for i < n {
		j := i
		// Identify sorted chunk [i, j]
		for j < n-1 && s[j] <= s[j+1] {
			j++
		}
		
		currBestR := -1
		// Iterate backwards in the chunk to find optimal r for each l
		for l := j; l >= i; l-- {
			if validR[l] {
				// Since we iterate downwards, the first valid R we encounter is the largest one
				if currBestR == -1 {
					currBestR = l
				}
			}
			
			validStart := (l == 0)
			if l > 0 && prefMax[l-1] <= s[l] {
				validStart = true
			}

			if validStart && currBestR != -1 {
				// l is start of sorted segment, currBestR is end
				// Prefix sort length l, Suffix sort length (n - 1 - currBestR)
				// Suffix length calculation: elements from currBestR+1 to n-1. Count = n - 1 - currBestR.
				slen := n - 1 - currBestR
				cost := int64(l)*int64(l) + int64(slen)*int64(slen)
				if cost < minCost {
					minCost = cost
				}
			}
		}
		i = j + 1
	}

	// Prepare for coordinate-based logic (BIT)
	elements := make([]Element, n)
	for idx, v := range s {
		elements[idx] = Element{idx, v}
	}
	sort.Slice(elements, func(i, j int) bool {
		return elements[i].val < elements[j].val
	})

	// Part 2: Type A (Overlap, Suffix Sort then Prefix Sort)
	// Iterate k (start of suffix sort).
	queriesA := make([]Query, 0, n+1)
	for k := 0; k <= n; k++ {
		val := -1
		if k > 0 {
			val = prefMax[k-1]
		}
		queriesA = append(queriesA, Query{k, val})
	}
	sort.Slice(queriesA, func(i, j int) bool {
		return queriesA[i].val < queriesA[j].val
	})

	bitA := NewBIT(n)
	elemPtr := 0
	for _, q := range queriesA {
		// Add elements strictly less than current max of prefix
		for elemPtr < n && elements[elemPtr].val < q.val {
			bitA.Add(elements[elemPtr].idx+1, 1)
			elemPtr++
		}
		k := q.k
		c := 0
		if k < n {
			c = bitA.QueryRange(k+1, n)
		}
		// i = k + c. Cost = i^2 + (n-k)^2
		iLen := k + c
		jLen := n - k
		cost := int64(iLen)*int64(iLen) + int64(jLen)*int64(jLen)
		if cost < minCost {
			minCost = cost
		}
	}

	// Part 3: Type B (Overlap, Prefix Sort then Suffix Sort)
	// Iterate i (length of prefix sort).
	queriesB := make([]Query, 0, n+1)
	for i := 0; i <= n; i++ {
		val := 2147483647
		if i < n {
			val = suffMin[i]
		}
		queriesB = append(queriesB, Query{i, val})
	}
	sort.Slice(queriesB, func(i, j int) bool {
		return queriesB[i].val < queriesB[j].val
	})

	bitB := NewBIT(n)
	elemPtr = 0
	for _, q := range queriesB {
		// Add elements less than or equal to current min of suffix
		for elemPtr < n && elements[elemPtr].val <= q.val {
			bitB.Add(elements[elemPtr].idx+1, 1)
			elemPtr++
		}
		i := q.k
		c := 0
		if i > 0 {
			c = bitB.QueryRange(1, i)
		}
		// j = n - c. Cost = i^2 + j^2
		jLen := n - c
		cost := int64(i)*int64(i) + int64(jLen)*int64(jLen)
		if cost < minCost {
			minCost = cost
		}
	}

	fmt.Println(minCost)
}
```