Cho số nguyên dương \(n\), hãy tính tổng dãy theo quy luật:

\(S = -1 + 2 - 3 + 4 - 5 + 6 - 7 + \dots + (-1)^n \times n\)

Yêu cầu

Tính tổng \(S\) theo công thức trên và in ra màn hình.

Dữ liệu nhập vào từ bàn phím

• Một dòng duy nhất chứa một số nguyên dương \(n\)
  \((1 \leq n \leq 10^6)\)

Kết quả in ra màn hình

• Một dòng duy nhất là giá trị tổng \(S\) tính được.

Ví dụ

Input

7

Output

-4

Giải thích

Dãy cần tính là: \(-1 + 2 - 3 + 4 - 5 + 6 - 7 = -4\)

Vào một buổi sáng anh Bo sắp một đàn bò gồm \(n\) con bò để vắt sữa. Anh dự kiến là vào sáng hôm đó, con bò thứ \(i\) có khả năng sẽ vắt được \(a_i\) lít sữa. Tuy nhiên đàn bò của anh có đặc tính là cứ mỗi lần vắt sữa một con, những con còn lại trông thấy sợ quá nên sẽ bị giảm sản lượng mỗi con 01 lít sữa. Nếu vắt sữa con bò thứ nhất, \(n-1\) con còn lại bị giảm sản lượng. Sau đó vắt sữa con bò thứ hai thì \(n-2\) con còn lại bị giảm sản lượng.... Bạn hãy giúp anh Bo tính xem thứ tự vắt sữa bò như thế nào để số lượng sữa vắt được là nhiều nhất nhé.

Input

• Nhập vào từ file "COW.INP"

• Dòng thứ nhất là số nguyên \(n\) là số lượng con bò \((1 \leq n \leq 10^5)\).

• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2,..., a_n\) là sản lượng sữa của các con bò \((1 \leq a_i \leq 10^6)\).

Output

• Đọc kết quả ra file "COW.OUT"
• Gồm 1 dòng duy nhất là số lít sữa nhiều nhất mà anh Bo có thể vắt được.

Sample Input 0

4
4 4 4 4

Sample Output 0

10

Cho số nguyên dương \(n\). Đếm số ước của \(n\) có ước số là \(2\).

Input

• \(t (t\le 100)\) - số test
• Mỗi test chứa \(1\) số nguyên dương \(n(n \le 10^9)\)

Output

• Số ước số thỏa mãn đề bài

Example

2
9
8 

0
3

Cho dãy số \(A\) chỉ gồm các số có giá trị 0 hoặc 1. Hãy đếm số lượt đổi chỗ ÍT NHẤT các phần tử để gộp được tất cả các số 1 trong dãy vào một miền liên tiếp?

Input

• Dòng đầu tiên gồm số nguyên \(N\) chỉ số phần tử thuộc dãy (\(1 \leq N \leq 10^6\)).
• Dòng thứ hai gồm \(N\) số nguyên thuộc mảng \(A\) (các phần tử cách nhau bởi dấu cách)

Output

• Số lượt đổi chỗ ít nhất.

Example

5
1 0 1 0 1

1

6
1 0 1 0 1 1

1

Trải qua kì thi quan trọng xong, Sắn về quê bắt tay làm kinh doanh với mảnh đất quê hương. Sắn bắt đầu làm nông trại với \(N\) chú bò sữa. Chú bò thứ \(i\) sản xuất \(a_i\) đơn vị sữa mỗi ngày.

Mỗi sáng sớm Sắn lùa lũ bò ra đồng cỏ để ăn những ngọn cỏ ngon nhất, tối Sắn lại lùa bò về chuồng. Lần này Sắn nâng cấp máy và mua thêm một máy nữa. Bây giờ Sắn có hai máy vắt sữa phục vụ để vắt hết \(N\) chú bò. Để đảm bảo công suất hoạt động của hai máy vắt sữa, mỗi lần vắt Sắn sẽ chia đều \(N\) chú bò vào hai máy sao cho lượng sữa hai máy vắt được tương đương nhau. Bạn hãy liệt kê cho Sắn biết tất cả cách sắp \(N\) chú bò vào hai máy để đạt được điều này.

Input

• Dòng thứ nhất chứa 1 số nguyên \(N\) \((1 \leq N \leq 20)\)
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots a_N (1 \leq a_i \leq 10^9)\), là sản lượng sữa của \(N\) chú bò.

Output

• Nếu không có cách nào thỏa mãn, hãy in ra \(-1\).
• Ngược lại hãy in ra mỗi đáp án trên 1 dòng riêng: Mỗi cách gồm \(N\) số nguyên \(x_1,x_2, \dots x_N, (x_i \in \{1,2\})\), là máy mà chú bò thứ \(i\) được phân vào. Các cách được in theo thứ tự từ điển.

Example

5
2 1 2 1 2 

11212
12122
12221
21112
21211
22121

5
2 1 2 1 8 

-1

5
1 5 1 3 4 

11122
22211

Marisa nuôi \(n\) con chim, con chim thứ \(i\) có kích cỡ \(a_i\). Một con chim có kích thước lớn hơn có thể ăn thịt con chim nhỏ hơn. Nếu con chim có kích cỡ \(a_i\) ăn thịt con chim kích cỡ \(a_j\), con chim lớn hơn sẽ có kích cỡ mới là \(a_i+a_j\).

Hãy xác định xem với mỗi con chim, có tồn tại trường hợp mà nó có thể trở thành con chim sống sót cuối cùng không?

Input

• Dòng đầu tiên là số nguyên \(n\), số lượng con chim.
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_i\) \((a_i \le 10^9)\).

Output

• In một xâu độ dài \(n\), vị trí thứ \(i\) là T nếu con chim thứ \(i\) có thể sống sót đến cuối, ngược lại in ra N.

Subtask

• Subtask \(1\) (\(40\%\) số điểm): \(1 \le n \le 1024\).
• Subtask \(2\) (\(60\%\) số điểm): \(1 \le n \le 5 \times 10^5\).

Sample Input 1

3
5 4 4

Sample Output 1

TNN

Vì vừa đạt giải cao trong một kì thi nên Hoàng Nhân được ban tổ chức trao thưởng. Thể lệ trao thưởng như sau:

• Có \(n\) bàn xếp thành một hàng ngang, trên mỗi bàn chứa một món quà.
• Hoàng Nhân được chọn bất kì món quà nào, hoặc không chọn, nhưng không được chọn quá 2 món quà liên tiếp.
  Bạn hãy giúp Hoàng Nhân tính xem có thể chọn lượng quà có giá trị lớn nhất là bao nhiêu.

Dữ liệu vào:

Vào từ file văn bản REWARD.INP gồm:

• Dòng đầu ghi số nguyên \(n\) \((n\leq10^5)\)
• Dòng thứ hai ghi \(n\) số nguyên \(A_1, A_2, \dots, A_n\) thể hiện giá trị của \(n\) món quà.

Dữ liệu ra:

Ghi ra file văn bản REWARD.OUT gồm một dòng duy nhất là kết quả của bài toán

10
8 4 57 46 62 19 14 6 26 3

178

Giới hạn:

• \(0 \leq \mid A_i \mid \leq 10^6\)
• Subtask 1 (40%): \(1\leq n\leq20\)
• Subtask 2 (60%): \(1\leq n\leq10^5\)

ami có một dãy số nguyên dương \(A\) và một số nguyên dương \(k\).

Nhận thấy dãy \(A\) không mang tính nghệ thuật, ami muốn tách dãy \(A\) thành một vài dãy con liên tiếp thoả mãn điều kiện sau:

• Mỗi một phần tử \(A_i\) đều thuộc một và chỉ một dãy con.
• Các phần tử trong cùng một dãy con phải có cùng giá trị.
• Độ dài một dãy con không vượt quá \(k\).

Các bạn hãy đếm xem có bao nhiêu cách khác nhau để ami có thể chia dãy thoả mãn các điều kiện trên. Hai cách chia gọi là khác nhau nếu tồn tại hai phần tử \(i\) và \(j\) khác nhau mà chúng ở chung một nhóm trong một cách, nhưng lại khác nhóm ở cách còn lại.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) là số phần tử của dãy \(A\).

• \(n\) dòng tiếp theo, mỗi dòng chứa \(1\) số nguyên dương \(A_i\) biểu thị một phần tử của dãy \(A\) \((1 \leq a_i \leq n)\).

• Dòng cuối cùng chứa số nguyên dương \(k\) là số phần tử tối đa trong một nhóm.

Output

• Hãy in ra số cách chia khác nhau thoả mãn điều kiện trên sau khi chia dư cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(1 \leq k \leq n \leq 300\).

• Subtask \(2\) (\(15\%\) số điểm): \(1 \leq k \leq n \leq 5000\).

• Subtask \(3\) (\(25\%\) số điểm): \(1 \leq k \leq n \leq 2*10^5\).

Example

4 
1 
2 
3
1
1

1

4 
2
3 
3
3
2

3

Lưu ý: 50% số test có \(n \leq 1000\).