There are N cities and two newly built cities X and Y among them (1 <=X<=Y<= N) There exists a road between cities:

i and i+1 for each 1 to N

X and Y.

The task is to tell for each k from 1 to N, the number of pairs of cities (such that the shortest path between city i and city is k

Consider the following example.

N number of cities-3

X, first special city-1

Y second special city-3

The pair of cities having the shortest distance-1 are (1,2) (1,3) and (2,3)

There is no pair of cities with the shortest distance-2.

There is no pair of cites with the shortest distance-2

Hence the answer returned is (3,0,0)

Can someone explain how to approach this problem?