점프 게임

길이가 $N$인 일직선 형태의 맵 $S$가 있다. 맵의 각 칸은 _ 또는 # 중 하나로 이루어져 있다. _는 착지할 수 있는 칸이고, #는 착지할 수 없는 칸이다. 첫 번째 칸과 마지막 칸은 항상 _이다.

플레이어는 첫 번째 칸에서 시작하여 마지막 칸까지 이동하려고 한다. 이동은 점프를 통해서만 할 수 있다. 현재 $i$번 칸에 있을 때, 양의 정수 $K$를 골라 $i+K$번 칸으로 점프할 수 있다. 단, $i+K\leq N$이어야 하며, 도착하는 칸은 _이어야 한다. 이때 점프 거리 $K$에 대한 비용은 $K^2$이다. 단, 점프하는 도중에 # 칸을 지나가는 것은 허용된다.

첫 번째 칸에서 마지막 칸까지 이동하는 데 필요한 최소 비용을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N$ $S$

첫째 줄에 첫 번째 칸에서 마지막 칸까지 이동하는 데 필요한 최소 비용을 출력한다.

• $2 \le N \le 200\ 000$.
• $S_i$는 _ 또는 #이다 $(1\le i\le N)$.
• $S_1$과 $S_N$은 _이다.