Cho mảng 1 chiều gồm n phần tử số nguyên. Hãy tính tổng các phần tử ở vị trí lẻ của mảng.

INPUT

Dòng đầu tiên là số nguyên ~n (2 \leq n \leq 10^6)~

Dòng tiếp theo chứa n số nguyên ~a_0,a_1,a_2,...,a_{n-1} (1 \leq a_i \leq 10^6)~

OUTPUT

Đáp án của bài toán

SAMPLE INPUT 1

5
1 2 3 4 5

SAMPLE OUTPUT 1

6

Cho mảng 1 chiều gồm n phần tử số nguyên. Hãy tính tổng các phần tử ở vị trí chẵn của mảng.

INPUT

Dòng đầu tiên là số nguyên ~n (2 \leq n \leq 10^3)~

Dòng tiếp theo chứa n số nguyên ~a_0,a_1,a_2,...,a_{n-1} (1 \leq a_i \leq 10^6)~

OUTPUT

Đáp án của bài toán

SAMPLE INPUT 1

5
1 2 3 4 5

SAMPLE OUTPUT 1

9

Cho mảng 2 chiều gồm n*m phần tử số nguyên. Hãy tính tổng các phần tử ~a_{i,j}~ sao cho i+j là số lẻ trong mảng.

INPUT

Dòng đầu tiên là số nguyên ~n~ và ~m~ ~(1 \leq n,m \leq 10^2)~

n dòng tiếp theo chứa m số nguyên ~a_{i,0},a_{i,1},a_{i,2},...,a_{i,m-1} (1 \leq a_i \leq 10^6)~

OUTPUT

đáp án của đề bài

SAMPLE INPUT 1

1 5
1 2 3 4 5

SAMPLE OUTPUT 1

6

SAMPLE INPUT 2

2 2
1 2
3 4

SAMPLE OUTPUT 2

5

Banmkh6 đang cần xây một căn nhà trên một mảnh đất hình chữ nhật.Với tham vọng to lớn đó, Banmkh6 quyết định xây một căn nhà là một khối hình hộp chữ nhật với chiều cao chiều rộng chiều dài lần lượt là h,a,b.

Hỏi thể tích căn nhà đó là bao nhiêu?

Input

Dòng đầu tiên chứa hai số nguyên h,a và b~(1 \leq h,a,b \leq 10^{4})~

Output

Thể tích căn nhà đó

Sample Input

2 3 4

Sample Output

24

Problem Statement

Bạn có một dãy số nguyên A có chiều dài là N . Tìm sự khác biệt giữa hiệu số tối đa của 2 yếu tố (với các chỉ số khách nhau ) trong ~A~ .

Ràng buộc

• ~2 \leq N \leq 100~
• ~1 \leq A_i \leq 10^9~
• Tất cả các giá trị đầu vào là số nguyên.

Input

Đầu vào tiêu chuẩn theo định dạng sau:

~N~

~A_1~ ~A_2~ ~...~ ~A_N~

Output

In ra sự khác biệt giữa hiệu số tối đa của 2 yếu tố (với các chỉ số khách nhau ) trong ~A~ .

Sample Input 1

4
1 4 6 3

Sample Output 1

5

Sự khác biệt hiệu số tối đa giữa 2 phần tử: ~A_3-A_1=6-1=5~ .

Sample Input 2

2
1000000000 1

Sample Output 2

999999999

Sample Input 3

5
1 1 1 1 1

Sample Output 3

0

Ở một hàm đệ qui, ta cần có 2 thứ: lời gọi hàm và điều kiện dừng.

Sau đây, Bob cho bạn một bài toán và Bob yêu cầu bạn hãy giải quyết nó bằng Đệ qui.

Cho 1 số nguyên n (Với 1≤n≤25). Bạn hãy lập trình đệ qui để tính số Fibonacci thứ n.

Biết số Fibonacci - https://vi.wikipedia.org/wiki/Dãy_Fibonacci - là số mà số sau bằng tổng 2 số trước. Bắt đầu với số thứ 1 là 1 và số thứ 2 cũng là 1.

Input

Dòng đầu tiên có chứa 1 số nguyên n (Với 1≤n≤25).

Output

Một dòng duy nhất là 1 số là số Fibonacci thứ n.

Examples

Input

1

Output

1

Input

2

Output

1

Input

3

Output

2

Input

4

Output

3