하이퍼클록

똑똑이 스머프는 하루가 너무 짧다고 결론지었다. 이대로라면 《똑똑이 스머프 어록》의 모든 권을 끝내 다 쓰지 못할 것 같았다. 그래서 그는 시간의 아버지를 찾아가 하루를 48시간으로 늘려 달라고 부탁했다. 시간의 아버지는 마뜩잖아 했지만, 똑똑이 스머프가 하도 조르는 통에 한 가지 조건을 걸고 승낙했다. 먼저 하이퍼클록 퍼즐을 풀어야 한다는 것이었다.

하이퍼클록은 $N$개의 시계로 이루어져 있다. 각 시계에는 바늘이 하나씩 있고, 시계판에는 숫자가 원형으로 적혀 있다. $i$번째 시계($1 \le i \le N$)의 시계판에는 $1$부터 $k_i$까지의 숫자가 원을 따라 적혀 있다. 처음에는 모든 바늘이 숫자 $1$을 가리킨다.

한 번의 이동에서는 시계 하나를 골라 그 바늘을 시계 방향 또는 반시계 방향으로 한 칸 돌린다. 시계판이 원형이므로 $1$번 자리와 $k_i$번 자리는 서로 이웃해 있어, 바늘이 둘 사이를 곧바로 오갈 수 있다.

배치란 $N$개의 바늘이 현재 가리키는 숫자들의 조합을 뜻한다. 가능한 배치는 정확히 $k_1 k_2 \cdots k_N$가지이다.

완전 순회란, 처음 배치(모든 바늘이 $1$을 가리키는 상태)에서 출발하여 가능한 모든 배치를 정확히 한 번씩 지나고, 마지막 이동을 마친 뒤 모든 바늘이 다시 처음 자리로 돌아오는 이동의 나열을 말한다. 이러한 순회의 길이가 얼마인지 똑똑이 스머프를 도와 알아내자.

첫째 줄에 시계의 개수인 양의 정수 $N$이 주어진다.

다음 $N$개의 줄에는 각각 정수 $k_i$($k_i > 1$)가 하나씩 주어진다. 이는 $i$번째 시계판에 적힌 숫자의 개수이다.

가능한 배치의 총수 $k_1 k_2 \cdots k_N$는 $10^6$을 넘지 않는다.

완전 순회는 항상 존재함이 알려져 있다. 하이퍼클록의 완전 순회에 필요한 이동 횟수를 정수 하나로 출력한다.