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ử trong 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

15

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ử trong đoạn từ ~l~ đến ~r~.

INPUT

Dòng đầu tiên lần lượt là 3 số nguyên ~n~ ~l~ ~r~ ~(2 \leq l \leq r \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 3
1 2 3 4 5

SAMPLE OUTPUT 1

9

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

Tìm phần tử nhỏ nhất trong dãy số A1, A2, .. An

Input Input số nguyên n đại diện cho số phần tử mảng và nhập giá trị cho các phần tử của mảng

Output
Output một dòng duy nhất phần tử nhỏ nhất trong mảng.

Examples

Input

3 
5 7 2

Output

2

Cho một mảng ~a~ gồm ~n~ phần tử, hãy tính tổng các số chẵn và tổng các số lẻ trong đoạn từ ~l~ đến ~r~ của mảng, trong đó chỉ số mảng được tính từ 1.

Giới hạn

• ~1 ≤ a_i ≤ 10^9~
• ~1 ≤ n ≤ 2 \times 10^5~
• ~1 ≤ l < r ≤ n~

Đầu vào

• Dòng đầu tiên: số nguyên ~n~
• Dòng thứ hai: ~n~ số nguyên ~a_i~, cách nhau bởi khoảng trắng
• Dòng thứ ba: hai số nguyên ~l~ và ~r~, cách nhau bởi khoảng trắng

Đầu ra

• Hai số nguyên cách nhau bởi khoảng trắng: tổng lẻ và tổng chẵn trong đoạn từ ~l~ đến ~r~

Sample Input

6
1 2 3 4 5 6
2 5

Sample Output

8 6

Bạn được giao một ma trận gồm ~n~ hàng và ~m~ cột, mỗi ô của ma trận đều chứa một số nguyên bí ẩn. Có hai cột ~l~ và ~r~, bạn cần khám phá tổng các giá trị từ cột thứ ~l~ đến cột thứ ~r~ trong ma trận. Nhiệm vụ này đòi hỏi sự tập trung để không bỏ sót bất kỳ giá trị nào trong khoảng đã cho.

Giới hạn

• ~1 ≤ n ≤ 10^3~
• ~2 ≤ m ≤ 10^3~
• ~1 ≤ a_{ij} ≤ 10^6~
• ~1 ≤ l < r ≤ m~

Đầu vào

• Dòng đầu tiên: hai số nguyên ~n~ và ~m~
• Tiếp theo: ~n~ hàng, mỗi hàng gồm ~m~ số nguyên ~a_{ij}~, cách nhau bởi khoảng trắng
• Dòng cuối cùng: hai số nguyên ~l~ và ~r~

Đầu ra

• Một số nguyên duy nhất: tổng các phần tử từ cột thứ ~l~ đến cột thứ ~r~

Sample Input

3 4
1 2 3 4
5 6 7 8
9 10 11 12
2 3

Sample Output

39

Cho một mảng có ~n~ giá trị, ~a_0, a_1, ..., a_{n - 1}~. Mentor Popi muốn các bạn thực hiện tính toán trên mảng này theo quy tắc như sau $$S = a_0 + a_1 - a_2 + a_3 - a_4 + \text{...} \pm a_{n-1}$$ Ví dụ: ~n = 5~, ~a = [1, 2, 3, 4, 5]~ ~\implies S = 1 + 2 - 3 + 4 - 5 = -1~

Input

• Dòng đầu tiên, gồm duy nhất một số nguyên ~n~ là kích thước của mảng.
• Tiếp theo, gồm ~n~ giá trị ~a_0, a_1, ..., a_{n - 1}~ đại diện cho ~n~ các giá trị của mảng.

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Constraints

• ~1 \le n \le 10^4~
• ~1 \le a_i \le 10^4~

Input Sample 1

5
1 2 3 4 5

Output Sample 1

-1

Input Sample 2

1
5

Output Sample 2

5

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ử trong mảng.

INPUT

Dòng đầu tiên là số nguyên ~n~ và ~m~ ~(2 \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

15

SAMPLE INPUT 2

2 2
1 2
3 4

SAMPLE OUTPUT 2

10

Mô tả vấn đề

Sử dụng mảng một chiều X[100] để lưu các số nguyên. Viết các hàm thực hiện các yêu cầu sau:

• Tính giá trị trung bình của mảng: m = ~\frac{x_0 + x_1 + x_2 + ... + x_{(n-1)}}{n}~

• Tính tổng bình phương: s = ~x_0^2~ + ~x_1^2~ + ~x_2^2~ + ... + ~x_{n-1}^2~

• Tính phương sai (Variance) d~^2~ = ~\frac{s}{n}~ - m~^2~

Input

Input gồm 2 dòng:

Dòng thứ nhất chứa duy nhất một số nguyên n (n ≤ 100)

Dòng thứ hai chứa n phần tử x~_0~, x~_1~, x~_2~, ..., x~_{n-1}~ của mảng

Output

Gồm 3 dòng:

Dòng thứ nhất là giá trị trung bình của mảng x. Làm tròn đến 1 chữ số thập phân.

Dòng thứ hai là tổng bình phương của mảng x.

Dòng thứ ba là phương sai của mảng x. Làm tròn đến 3 chữ số thập phân.

Sample Input 1

3
1 2 3

Sample Output 1

2.0
14
0.667

Vì những câu chuyện cổ tích quá dài, AliVu đã yêu cầu mình viết lại ngắn gọn và dễ hiểu. Nhiệm vụ của bạn là viết chương trình kiểm tra xem một mảng số nguyên có phải là mảng đối xứng hay không.

Chú ý: Mảng đối xứng là mảng mà thứ tự các phần tử từ đầu đến cuối giống hệt thứ tự từ cuối về đầu.

Input

• Dòng đầu tiên là một số nguyên ~n~ ~(1 \le n \le 10^3)~ - sô phần tử của mảng.
• Dòng thứ hai chứa n số nguyên ~a_1,a_2,a_3,...,a_n~ ~(1 \le a_i \le 10^3)~ - các phần tử của mảng.

Output

• In YES nếu là mảng đối xứng. Ngược lại, in NO.

Sample Input 1

5
1 2 3 2 1

Sample Output 1

YES

Sample Input 2

4
1 2 3 4

Sample Output 2

NO

Mô tả vấn đề

Viết chương trình nhập một dãy số nguyên A có n phần tử từ bàn phím. In ra số lượng số nguyên tố có trong mảng.

*Note: * Số nguyên tố là số lớn hơn hoặc bằng 2, và có chia hết cho 1 và chính nó.

Input

Dòng đầu tiên là số nguyên n (n ≤ 1000).

Dòng thứ hai là dãy các số nguyên ~A1~, ~A2~, ... ~An~ (1 ≤ ~Ai~ ≤ 10000)

Output

In ra kết quả

Sample Input

6
2 6 7 10 5 4

Sample Output

3

Có 3 số nguyên tố trong mảng là 2, 7, 5.

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

Cho một ma trận (mảng 2 chiều) kích thước ~n~ x ~m~, ~a_{i, j}~ là giá trị tại hàng ~i~ và cột ~j~. Mentor Popi muốn biết rằng có bao nhiêu vị trí ~i~, ~j~ sao cho ~a_{i, j}~ là bội của ~i + j~.

Chú ý: Các chỉ số của mảng bắt đầu từ ~1~.

Ví dụ: ~n = 3~, ~m = 3~ và ma trận ~a = \begin{bmatrix} 1&2&3\\3&2&1\\2&4&6 \end{bmatrix}~, Ta có các vị trí thỏa mãn như sau: ~(2, 1)~, ~(3, 3)~. Vậy số lượng vị trí thỏa mãn là ~2~.

Input

• Dòng đầu tiên, gồm cặp số nguyên ~n~ và ~m~ là kích thước của ma trận.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~m~ giá trị ~a_{i, 1}, a_{i, 2}, ..., a_{i, m}~ đại diện cho ~m~ các giá trị của hàng thứ ~i~.

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Constraints

• ~1 \le n, m \le 50~
• ~1 \le a_i \le 10^4~

Input Sample 1

3 3
1 2 3
3 2 1
2 4 6

Output Sample 1

2

Input Sample 2

3 3
1 2 3
3 4 1
2 4 6

Output Sample 2

3

Cho một mảng a gồm n phần tử ~a_1~, ~a_2~, ...~a_n~. Trong một bước bạn có thể tăng giá trị của một phần tử bất kỳ trong mảng lên 1 đơn vị. Bạn hãy tính số bước ít nhất để tạo ra mảng a gồm các phần tử tăng dần.

Mảng a tăng dần là mảng có các phần tử ~a_1~ ≤ ~a_2~ ≤ ... ≤ ~a_n~

Input

Gồm 2 dòng:

Dòng thứ nhất là một số nguyên n.(1 ≤ ~n ≤ 10^5~)

Dòng thứ hai là dãy số ~a_1~, ~a_2~, ...~a_n~ cách nhau bởi dấu cách. (1 ≤ ~a_i~ ≤ ~10^9~)

Output

Một dòng duy nhất là

Examples

Input

6
3 1 5 4 8 9 

Output

3 

*Note: *chúng ra tăng phần tử thứ 2 lên 2 đơn vị, phần tử thứ 4 lên 1 đơn vị.

Mô tả vấn đề

Cho hai mảng A, B là hai tập hợp, cả 2 có kích thước n nhập từ bàn phím. Tạo mảng C là một tập hợp gồm các phần tử:

• Xuất hiện trong cả A và B.

• Xuất hiện trong A nhưng không xuất hiện trong B.

• Xuất hiện trong B nhưng không xuất hiện trong A.

Input

Dòng thứ nhất là một số duy nhất n (n ≤ 100).

Dòng thứ hai là các phần tử A~_1~, A~_2~, ... A~_n~ của mảng A (1 ≤ ~A_i~ ≤ 1000).

Dòng thứ ba là các phần tử B~_1~, B~_2~, ... B~_n~ của mảng B (1 ≤ ~B_i~ ≤ 1000) ..

Output

Gồm 3 dòng:

Dòng thứ nhất là các phần tử xuất hiện trong cả A và B.

Dòng thứ hai là các phần tử xuất hiện trong A nhưng không xuất hiện trong B.

Dòng thứ ba là các phần tử xuất hiện trong B nhưng không xuất hiện trong A.

Đảm bảo tất cả các phần tử trong mảng A và B là phân biệt.

Sample Input 1

5 
1 2 3 4 5 
3 4 8 9 1

Sample Output 1

1 3 4
2 5
8 9