NKOJ 3937: Why Cows Cross Roads (tree structure)

P3937为何奶牛要穿过马路1

问题描述

在约翰的农场中，有一条笔直且宽阔的道路横穿而过。道路的一侧整齐排列着N个牛棚，编号从1到N，每个牛棚内分别居住着一头编号相同的奶牛，确保每个牛棚仅容纳一头牛。道路的另一侧同样设有N个牛棚，编号也是1到N，且每个牛棚内也居住着一头对应编号的奶牛。由于相同编号的奶牛经常需要跨越道路去拜访它们的同伴，这种频繁的穿越行为导致了严重的交通拥堵。具体而言，当两头不同编号的奶牛同时穿越道路时，如果它们的行进路线在空间中发生交叉，就会发生碰撞事故。约翰希望优化牛棚的布局，以最大限度地减少此类交叉线路，从而降低碰撞风险。

约翰计划采用“循环移位”的策略来重新安排牛棚的位置。所谓循环移位，是指将某一侧的牛棚序列整体向右或向左移动若干位，移出的部分会绕回到序列的另一端。例如，假设道路一侧有7个牛棚，当前居住的奶牛编号依次为3、7、1、2、5、4、6。如果约翰决定将该侧序列向右移动2个位置，那么移位后的新顺序将变为4、6、3、7、1、2、5。需要注意的是，约翰只能选择对道路的一侧牛棚进行移位操作，而不能同时移动两侧。

你的任务是帮助约翰计算，通过仅对其中一侧牛棚进行任意次数的循环移位，能够达到的最少交叉线路数是多少。请输出这个最小值。

输入格式

第一行包含一个整数N，表示牛棚的数量（1