Binary search with alternative comparison cost

I have a sorted array $A$ of non-arbitrary elements. Now, I have another element $c$ and I want to find out where it belongs in the sorting of $A$. The cost of comparing $c$ to $A_i$ is $\Theta(i^2)$. I do not directly care about the number of comparisons, I just want to minimize the sum of the costs of the comparisons in the expected case (worst-case would also be nice).

Let's assume that each element in $A$ is unique and that $A$ does not contain $c$.

What is the optimal algorithm?

Let's say I told you in advance that $c$ is in the larger half. You still need $\Omega(\log n)$ comparisons, while now every helpful comparison takes $\Omega(n^2)$ cost, so the cost is always $\Omega(n^2\log n)$, which can be achieved with simple binary search.

StackExchange Computer Science Q#95587, answer score: 3