Bessie mới phát hiện rằng nghệ sĩ nhạc pop yêu thích của cô, Elsie Swift, đang biểu diễn trong chuyến lưu diễn "Eras Tour" mới của mình! Thật không may, vé đang bán rất nhanh, vì vậy Bessie đang nghĩ đến việc bay tới một thành phố khác để tham dự buổi hòa nhạc. Chuyến lưu diễn "Eras" đang diễn ra tại \(N\) \((2 \leq N \leq 750)\) thành phố được đánh số từ 1 đến \(N\), và đối với mỗi cặp thành phố \((i,j)\) với \(i < j\), có thể tồn tại một chuyến bay trực tiếp từ \(i\) đến \(j\) hoặc không.

Một tuyến bay từ thành phố \(a\) đến thành phố \(b\) \((a < b)\) là một dãy gồm \(k \ge 2\) thành phố \(a = c_1 < c_2 < \dots < c_k = b\) sao cho đối với mỗi \(1 \le i < k\), tồn tại một chuyến bay trực tiếp từ thành phố \(c_i\) đến thành phố \(c_{i+1}\).

Đối với mỗi cặp thành phố \((i,j)\) với \(i < j\), bạn được cung cấp độ chẵn/lẻ (parity) của số lượng tuyến bay giữa chúng (0 là chẵn, 1 là lẻ).

Trong khi lên kế hoạch cho chuyến đi, Bessie bị phân tâm và bây giờ muốn biết có bao nhiêu cặp thành phố có chuyến bay trực tiếp giữa chúng. Có thể chứng minh rằng đáp án là duy nhất.

Input

• Dòng đầu tiên chứa \(N\).
• Sau đó là \(N-1\) dòng. Dòng thứ \(i\) chứa \(N-i\) số nguyên. Số nguyên thứ \(j\) của dòng thứ \(i\) bằng với độ chẵn/lẻ của số tuyến bay từ thành phố \(i\) đến thành phố \(i+j\).

Output

• In ra số lượng cặp thành phố có chuyến bay trực tiếp giữa chúng.

Scoring

• Subtask \(1\): \(N \leq 6\)
• Subtask \(2\): \(N \leq 100\)
• Subtask \(3\): Không có ràng buộc thêm.

Example

3
1 1
1

2

5
1 1 1 1
1 0 1
0 1
1

6