Cho một dãy gồm ~n~ ô, mỗi ô có ~a_i~ viên kẹo.

Bạn có thể thao tác trên các ô như sau: lấy hai cái kẹo ở ô ~x~ và bỏ vào ô ~x-1~ một cái kẹo. Hãy cho biết số kẹo lớn nhất ô ~a_1~ có thể có là bao nhiêu.

Input

• Dòng đầu gồm số tự nhiên ~n~ (~1 \le n \le 10^5~) - là số ô của dãy.

• Dòng thứ hai gồm ~n~ số tự nhiên ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^6~) - là số kẹo từng ô.

Output

• Một dòng duy nhất là số kẹo lớn nhất ô ~1~ có thể có.

Scoring

Sample Input 1

3
2 1 2

Sample Output 1

3

Cho dãy ~a~ gồm ~n~ số nguyên ~a_0,a_1,\dots,a_{n-1}~ ~(0\leq a_i\leq 1)~. Ta sắp xếp lại dãy ~a~ theo thứ tự tăng dần bằng thuật toán Bubble sort được mô tả như bên dưới.

sorted = false 
while (sorted == false):
    sorted = true
    for i = 0 to n - 2:
    if a[i + 1] < a[i]:
        swap(a[i + 1], a[i])
        sorted = false

Trong đó câu hàm ~swap~ là hàm đổi giá trị của ~2~ biến.

Hãy cho biết số lần lệnh ~swap~ được dùng.

Input

• Dòng đầu chứa số nguyên ~n~ là độ dài của dãy số ~(1\leq n \leq 10^6)~.

• Dòng thứ hai chứa ~n~ số nguyên ~a_0,a_1,\dots,a_{n-1}~ ~(0\leq a_i \leq 1)~

Output

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

Sample Input 1

5
1 0 1 0 1

Sample Output 1

3

Notes

• ~30\%~ số test có ~n \leq 3000~

• ~70\%~ số test còn lại không có ràng buộc gì thêm.

Ở trường mẫu giáo, nkwn đang được dạy về cách ghép những chữ số. Thầy giáo của nkwn muốn giao cho cả lớp bài tập như sau:

Cho một dãy ~A~ gồm ~n~ số tự nhiên từ ~0~ đến ~9~ và một số ~k~. Hỏi có bao nhiêu dãy con của ~A~ gồm ~k~ phần tử, mà các phần tử của dãy con này hợp lại thành 1 số chẵn có nghĩa? Biết một số được gọi là số có nghĩa khi số đó không có chữ số ~0~ đứng đầu nếu số đó là số có nhiều hơn 1 chữ số.

Nhưng bạn nkwn mải chơi nên quên hoàn thành bài tập. nkwn không muốn bị thầy mắng, nên nhờ bạn giúp đỡ bạn ấy hoàn thành nhé!

Dãy con (subsequence) là dãy có thể được suy ra từ dãy đã cho bằng cách xóa một số hoặc không có phần tử nào mà không thay đổi thứ tự của các phần tử còn lại. Ví dụ, dãy ~(1, 2, 5)~ là dãy con của dãy ~(1, 2, 3, 4, 5)~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~, là độ dài dãy ~A~.
• Dòng thứ hai chứa ~n~ số tự nhiên ~A_i (0 \le A_i \le 9)~, mỗi số được ngăn cách với nhau bằng một dấu cách.
• Dòng thứ ba chứa số ~k~ ~(1 \le k \le 30)~ là độ dài của dãy con.

Output

• In ra một dòng duy nhất chứa số lượng dãy con tạo thành số chẵn có nghĩa modulo ~10^9 + 7~.

Scoring

• ~40\%~ số test có ~1 \le n \le 20~.
• ~60\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

5
1 1 0 1 0
3

Sample Output 1

6

Notes

• Ở test ví dụ, ta có thể thấy có ~6~ dãy con tạo nên số chẵn có nghĩa:

~[1 , 2 , 3] = 110~.

~[1 , 2 , 5] = 110~.

~[1 , 3 , 5] = 100~.

~[1 , 4 , 5] = 110~.

~[2 , 3 , 5] = 100~.

~[2 , 4 , 5] = 110~.

Bé Lợi hôm nay đi tập bắn súng. Trong trường súng có ~n~ tấm bia, tấm bia thứ ~i~ bắt đầu ở vị trí ~a_i~ và kết thúc ở vị trí ~b_i~.

Với uy lực của khẩu AK-47, mỗi viên đạn của khẩu súng có đủ uy lực để xuyên qua tất cả các tấm bia nằm trên quỹ đạo của nó. Khi một viên đạn được bắn ở vị trí ~x~, tất cả các tấm bia có ~a_i \leq x \leq b_i~ sẽ được tính là bị bắn trúng.

Hỏi với hai phát bắn, bé Lợi có thể bắn trúng tối đa bao nhiêu tấm bia? Nếu một tấm bia trúng hai phát đạn, nó cũng chỉ được tính 1 lần.

Input

• Dòng đầu nhập số nguyên ~n~ ~(1 \le n \le 10^5)~ là số tấm bia ở trong trường bắn.

• Dòng thứ ~i~ trong ~n~ dòng tiếp theo nhập hai số nguyên ~a_i, b_i~ ~(-10^5 \le a_i < b_i \le 10^5)~ mô tả tấm bia thứ ~i~.

Output

• In ra số lượng tấm bia lớn nhất có thể bị Lợi bắn trúng sau hai phát.

Scoring

• ~30\%~ số test thoả mãn ~n \le 100~.

• ~30\%~ số test khác có ~n \le 1000~.

• ~40\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

5
1 2
2 3
3 4
4 5
5 6

Sample Output 1

4

Notes

• Lợi bắn vào hai vị trí ~2~ và ~4~. Khi đó tập các tấm bia bắn trúng (đánh số từ ~1~) sẽ là: ~\{1, 2, 3, 4\}~

Cho một dãy số nguyên ~a~ kích thước ~n~ bao gồm toàn các phần tử không âm.

Người ta thực hiện lần lượt các truy vấn sau thuộc một trong ba dạng sau trên dãy:

• ~1~ ~l~ ~r~ ~x~: Gán ~a_i=a_i~ AND ~x~ với mọi ~l\le i \le r~.

• ~2~ ~l~ ~r~ ~x~: Gán ~a_i=x~ với mọi ~l\le i \le r~.

• ~3~ ~l~ ~r~: Tính giá trị ~a_l~ OR ~a_{l+1}~ OR ~...~ OR ~a_r~.

Trong đó AND là toán tử AND và OR là toán tử OR.

Yêu cầu: Bạn hãy cho biết người ta ở đây là ai trả lời giá trị của biểu thức ở các truy vấn loại 3 nhé.

Input

• Dòng đầu chứa hai số nguyên dương ~n, q~ (~1\le n,q \le 5\cdot10^5~) là kích thước dãy và số truy vấn.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~0\le a_i < 2^{30}~) mô tả dãy số.

• ~q~ dòng tiêp, mỗi dòng chứa một truy vấn thuộc một trong ba dạng kể trên. Trong mọi truy vấn luôn có ~1\le l \le r \le n~; trong truy vấn 1 và 2 luôn có ~0 \le x < 2^{30}~.

Output

In ra nhiều dòng, mỗi dòng là câu trả lời cho các truy vấn loại 3 tương ứng.

Scoring

• Có ~20\%~ số test của bài với ~n,q\le 5000~.

• Có ~20\%~ số test khác của bài không có các truy vấn loại 1.

• Có ~20\%~ số test khác của bài với ~n,q \leq 10^5~

• ~40\%~ số test còn lại không có điều kiện gì thêm.

Sample Input 1

5 6
1 2 3 4 5
3 1 5
3 2 3
1 1 5 1
3 1 5
2 3 4 4
3 2 3

Sample Output 1

7
3
1
4

Notes

Sau truy vấn loại 1, dãy ~a~ trở thành:

~[1, 0, 1, 0, 1]~

Sau truy vấn loại 2, dãy ~a~ trở thành:

~[1, 0, 4, 4, 1]~