Convex Hull Perimeter of Arranged Geometric Figures

Given a sequence of geometric figures placed in contiguous grid cells in one row (from left to right), compute the perimeter of the convex hull of their union. Each cell is a unit square (with side length \(1\)). In each cell, there is exactly one figure, which can be one of the following:

1. A square that exactly fills the cell.
2. A circle inscribed in the cell. (Its center is at \((i+0.5, 0.5)\) and its radius is \(0.5\), if the cell’s left-bottom corner is at \((i,0)\).)
3. An equilateral triangle whose base coincides with the bottom side of the cell. (Its vertices are \((i, 0)\), \((i+1, 0)\), and \((i+0.5, \frac{\sqrt{3}}{2})\).)

The figures are placed in cells with indices \(0,1,2,\dots, n-1\) (from left to right). Note that for the square the entire cell \([i,i+1] \times [0,1]\) is filled; for the circle only the inscribed circle is drawn; and for the triangle, only the triangle is drawn. It is guaranteed that the figures in adjacent cells are placed without gaps. Output the perimeter of the convex hull of the union of these figures.

inputFormat

The input consists of two lines:

1. The first line contains an integer \(n\) (the number of cells).
2. The second line contains a string of length \(n\). Each character is one of 1, 2, or 3 representing the shape in the corresponding cell: 1 for a square, 2 for a circle, and 3 for an equilateral triangle.

outputFormat

Output a single number: the perimeter of the convex hull of the union of the given figures. Print the answer with at least 6 decimal places of precision.

sample

1
1

4.000000