Minimum Highway Construction Cost

You are given an integer n representing the number of cities in each row and column of a grid (i.e. an n x n grid). Each cell in the grid represents a city. Highways can be built between any two horizontally or vertically adjacent cities.

The cost to build a highway between two adjacent cities is 1 unit. In order to ensure that there exists a path between any two cities in the grid, you need to build a minimum set of highways. It can be shown that the minimum total cost required is given by the formula:

$$ f(n) = 2n(n-1) $$

Your task is to compute and output the minimum total highway construction cost for a given grid size n x n.

inputFormat

The input consists of a single integer n (where 1 ≤ n ≤ 10⁶) provided via standard input. It represents the number of cities in each row and column of the grid.

outputFormat

Output a single integer representing the minimum total cost required to build the highways such that there is a path between any two cities in the grid.

1

0