A turnpike consists of N$-1$ stretches of road between N toll stations; each stretch has an associated cost of travel and the cost of travel between two toll stations is the sum of the costs of the stretches traveled. For example,

$5749$

$|-----|-------|----|---------|$

$12345$

represents a turnpike with N $=5$ toll stations numbered $1$ through $5$ and four road stretches with associated costs $5,7,4,$ and $9.$ The cost of traveling from toll station $2$ to toll station $5$ is $20,$ for example.

Design a O$(1)$ time algorithm that computes the cost of going between any two stations i and j using a pre$-$computed two$-$dimensional array with O$($N$2)$ entries. What should this table contain?