Cho một dãy gồm ~n~ số nguyên dương, các phần tử được đánh số thứ tự từ 1 đến ~n~. Một phần tử được gọi là phần tử trung bình nếu nó có hai phần tử kề bên và bằng trung bình cộng của hai phần tử kề bên của nó, phần tử thứ i có hai phần tử kề bên là phần tử thứ ~i-1~ và phần tử thứ ~i+1~.

Yêu cầu: Xác định xem có bao nhiêu phần tử trung bình trong dãy số này.

Input

• Dòng thứ nhất ghi số nguyên dương ~n~ (~n≤10^3~)

• Dòng thứ hai ghi ~n~ số nguyên dương ~a_i~ (~1≤a_i≤10^3~).

Output

• Một số duy nhất là kết quả tìm được.

Example

Input

8
2 2 2 5 8 3 5 7

Output

3

Cho một dãy gồm ~n~ số nguyên dương.

Yêu cầu: Xác định số cách chọn hai phần tử trong dãy số sao cho tổng hai phần tử này có giá trị lẻ.

Input

• Dòng thứ nhất ghi số nguyên dương ~n~ (~1≤n≤10^6~).

• Dòng thứ hai ghi ~n~ số nguyên dương ~a_i~ (~1≤a_i≤10^6~).

Output

• Một số là kết quả tìm được.

Examples

Input1

4
1 3 5 6

Output1

3

Input2

5
2 4 7 8 6

Output2

4

Note

• Giải thích ví dụ 1: Các cặp số được chọn là (1;6),(3;6),(5;6).

• Giải thích ví dụ 2: Các cặp số được chọn là (2;7),(4;7),(7;8),(7;6).

cho ba số tự nhiên ~a~, ~b~ và ~n~. Gọi ~S~ là tổng các số tự nhiên nhỏ hơn ~n~, sao cho các số đó chia hết cho ~a~ nhưng không chia hết cho ~b~.

Yêu cầu: Viết chương trình xuất ra màn hình giá trị ~S~.

Input

• Dòng thứ nhất là số tự nhiên ~a~ (~1≤a≤10^4~).
• Dòng thứ hai là số tự nhiên ~b~ (~1≤b≤10^4~).
• Dòng thứ ba là số tự nhiên ~n~ (~1≤n≤10^9~).

Output

• Xuất ra màn hình giá trị ~S~.

Example

Input

2
3
9

Output

14