Passing Cars

Przemek watches the cars on a road. The road is two-way and connects the eastern side of the city with the western side. Standing on a hill, Przemek can see the exact position of every car.

He wants to know how many pairs of cars will pass each other. Two cars pass each other when they drive in opposite directions and, of the two, the one that is further west is heading east while the one that is further east is heading west, so they move toward each other and cross. Assume the cars never turn around, never overtake, and always drive straight ahead.

Given the driving directions of the cars listed from west to east, count how many pairs of cars will pass each other.

The first line contains an integer $n$ ($1 \le n \le 10^6$), the number of cars.

The second line contains $n$ integers $s_1, s_2, \dots, s_n$ (each $s_i \in \{0, 1\}$). The cars are given in order from the westmost to the eastmost (car $i$ is further west than car $i+1$), and $s_i$ is the driving direction of car $i$: $s_i = 0$ means the car drives east, and $s_i = 1$ means the car drives west.

Print a single integer: the number of pairs of cars that will pass each other.

A pair $(i, j)$ with $i < j$ passes if and only if car $i$ drives east (0) and car $j$ drives west (1). So the answer equals the number of ordered pairs in which a 0 appears before a 1. Scan from the left, keep a running count of the east-bound (0) cars seen so far, and add that count to the answer every time you meet a west-bound (1) car.