There is a straight snowy road, divided into n blocks. The blocks are numbered from 1 to n from left to right. If one moves from the i-th block to the (i 1)-th block, he will leave a right footprint on the i-th block. Similarly, if one moves from the i-…