(Analysis by Nick Wu)

We start by presenting an $O(N^2)$ brute force algorithm - for a given cow, we can scan over all the other cows and count the number of cows taller than the given cow on both sides and then determine if the cow is unbalanced.

One possible improvement we could do is sort the cows in decreasing order of height. If we process the cows in that order, then we can maintain the indices of all the taller cows. This only improves the performance of the algorithm by a constant factor. However, we will use this change in algorithm to present an $O(N \log N)$ solution.

When we maintain the indices of all the taller cows, we would like to be able to efficiently query for how many indices are less than a given index, and to also be able to insert an index into this collection. More precisely, our data structure needs to efficiently support the following operations:

$Insert(x)$: Insert $x$ into the data structure.

$LessThan(x)$: Count how many numbers in the data structure are less than $x$.

We will use a data structure known as a Fenwick tree, or a binary indexed tree, to support these two operations. A Fenwick tree operates on an internal array of integers $a_1, \dots, a_N$ and supports two operations in $O(\log N)$:

$Update(x, v)$: Increase $a_x$ by $v$.

$Query(x)$: Return $\displaystyle\sum_{i=1}^x a_i$.

Our approach is as follows: Imagine that we have sorted the cows in decreasing height, and initialize a sequence $a_1$ through $a_N$ to be zero everywhere. Imagine that we are considering the $k$th tallest cow which is at index $i$. We compute $L_k = Query(i)$ and $R_k = k-1-L_k$. If $\displaystyle\frac{\max(L_k, R_k)}{\min(L_k, R_k)} > 2$, then we assert that cow $k$ is unbalanced. Finally, we set $a_i = 1$ by calling $Update(i, 1)$.

In this approach, we maintain the invariant that $a_i = 1$ if and only if every cow being considered from the moment $a_i$ is set to 1 is shorter than the cow at index $i$. The Fenwick tree lets us efficiently query for the number of cows to the left of the given cow that are taller than it.

import java.io.*;
import java.util.*;
public class bphoto {
public static void main(String[] args) throws IOException {
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("bphoto.out")));
int n = Integer.parseInt(br.readLine());
State[] l = new State[n];
for(int i = 0; i < n; i++) {
l[i] = new State(Integer.parseInt(br.readLine()), i);
}
Arrays.sort(l);
int ret = 0;
int seen = 0;
BIT bit = new BIT(n);
for(State curr: l) {
int lhs = bit.query(curr.index);
int rhs = seen - lhs;
if(Math.max(lhs, rhs) > 2 * Math.min(lhs, rhs)) {
ret++;
}
bit.update(curr.index, 1);
seen++;
}
pw.println(ret);
pw.close();
}

static class State implements Comparable<State> {
public int height, index;

public State(int height, int index) {
super();
this.height = height;
this.index = index;
}
public int compareTo(State s) {
return s.height - height;
}
}

static class BIT {
public int[] tree;
public BIT(int n) {
tree = new int[n+5];
}
public void update(int index, int val) {
index++;
while(index < tree.length) {
tree[index] += val;
index += index & -index;
}
}
public int query(int index) {
int ret = 0;
index++;
while(index > 0) {
ret += tree[index];
index -= index & -index;
}
return ret;
}
}

}