After years of investigation and pursuit, the fugitive Miguelez, accused of high treason against USP (Union of Solar Planets), was captured by the famous space detective Morete. Due to the gravity of his crime, he was sent to the maximum-security prison on Neptune, which employs the panoptic system: all 360 cells of the complex are arranged along a circle, numbered from 1 to 360, with the watchtower located at the center of this circle, allowing the prison guard to see all the cells.
Detective Morete is concerned that Miguelez may plot an escape, so he wants to enhance surveillance of the prison cells by installing a new set of cameras in the watchtower, which will cover a single contiguous interval of cells. Morete has access to the record of which cells are occupied in the complex and wants to install the cameras in such a way that they cover the entire set of these cells; however, due to budget constraints, he wants to determine the size of the smallest interval of cells that need to be monitored to ensure all occupied cells are observed.
Busy with his duty to uphold the law, Morete has requested your assistance: given the $$$n$$$ cells $$$c_i$$$ in the circle that are occupied, what is the minimum number of cells that should be covered by the cameras so that all occupied cells are under surveillance?
The first line of input has as integer $$$n$$$ ($$$1 \le n \le 360$$$) — the number of occupied celss.
The second line of input has $$$n$$$ distinct integers $$$c_i$$$ ($$$1 \le c_i \le 360$$$) — the number of the $$$i$$$-th occupied cell.
The output should contain a single integer, which is the size of the smallest interval of cells that should be covered by the cameras.
22 32
31
310 330 30
61
In the first test case from the examples, the smallest contiguous interval that satisfies the statement is from cell 2 to 32, covering 31 cells.
In the second test case from the examples, the smallest contiguous interval that satisfies the statement is from cell 330 to 30, totaling 61 cells.