Вася с недавнего времени начал посещать кружок по программированию. Оказалось, что в нем занимается довольно много талантливых школьников. Ребята быстро сдружились и всегда ходили домой вместе, пока это позволял маршрут. Маршрут каждого участника кружка пролегает через череду перекрестков. Будучи крайне вежливыми, ребята всегда прощаются друг с другом посредством рукопожатий, когда их пути на каком-либо перекрестке расходятся. Более того, может получиться так, что ребята снова могут пересечься на каком-нибудь последующем перекрестке, и тогда они снова здороваются также посредством рукопожатий. Когда какой-либо участник завершает свой маршрут и заходит домой, он прощается с остальными также посредством рукопожатия.

Вася обратил внимание на столь увлекательный процесс, и ему стало интересно, а какое суммарное количество рукопожатий происходит, пока все ребята не доберутся домой.

Васе известен маршрут каждого из участников кружка. Маршрут представляет собой последовательность перекрестков, между которыми перемещаются ребята. Перекрестки пронумерованы от $1$ до $N$. Все ребята движутся с одинаковой скоростью. Считать, что на преодоление расстояния между любыми двумя перекрестками все участники тратят одинаковое время. Гарантируется, что все маршруты начинаются на перекрестке $1$. Если в маршруте какого-либо участника встречается два одинаковых перекрестка подряд, это означает, что участник стоит на этом перекрестке количество времени, требуемое на преодоление расстояния между двумя различными перекрестками.

Помогите Васе ответить на интересующий его вопрос.