Yêu cầu:

Tèo là một cậu bé rất khỏe nhưng cũng cực kỳ lười biếng. Hôm nay, Tèo được phú ông giao cho nhiệm vụ vào rừng đốn củi. Phú ông đưa cho Tèo một danh sách gồm n cây của phú ông muốn đốn. Mỗi cây khi đốn sẽ mang lại cho Tèo ai bó củi. Những cây nào không đốn thì không được bó củi nào. Nếu Tèo đốn được ít nhất một nửa tổng số bó củi theo yêu cầu trong buổi sáng, thì sẽ được phú ông thưởng cho một bữa cơm trưa no nê. Ví dụ, nếu có ~3~ cây trong danh sách, tương ứng cho ~1~, ~3~ và ~4~ bó củi, thì tổng số là ~8~ bó, và chỉ cần đốn đủ ~4~ bó là đủ điều kiện để được thưởng. Tèo rất khỏe mạnh, có thể đốn bất kỳ cây nào mà không gặp khó khăn. Nhưng cậu lại rất lười, nên muốn đốn ít cây nhất có thể để vẫn được bữa cơm trưa ngon lành.

Tèo chỉ muốn đốn liền mạch một đoạn cây nào đó trong danh sách. Tức là Tèo chọn một cây số hiệu ~k~, rồi lần lượt đốn các cây số ~k, k+1, k+2,… ,~ cho đến khi vừa đủ số bó củi tối thiểu theo yêu cầu. Tuy nhiên, để giảm bớt công sức, Tèo có thể chọn bỏ qua nhiều nhất một cây trong đoạn đó, nếu việc bỏ cây đó giúp giảm số lượng cây phải đốn mà vẫn đảm bảo đủ chỉ tiêu.

Hãy xác định số lượng cây ít nhất mà Tèo cần đốn (theo chiến lược lười biếng của mình) để được phần thưởng từ phú ông.

Dữ liệu:

• Dòng thứ nhất là số nguyên ~n (1 ≤ 𝑛 ≤ 10^5)~
• Dòng tiếp theo ghi các số nguyên ~a_i~ là số bó củi khi đốn được cây thứ ~i (1≤a_i≤10^9 )~

Kết quả:

• Một dòng ghi số cây ít nhất mà Tèo cần phải đốn để đạt chỉ tiêu của Phú ông.

Input 1:

5
1 1 2 1 2

Output 1:

2

Input 2:

3
2 3 1

Output 2:

1

Giải thích

Ví dụ 1: Tèo có thể chọn đoạn gồm các cây [2 1 2] để đốn và có thể bỏ qua cây [1] mà vẫn có thể đảm bảo số lượng bó củi tối thiểu theo yêu cầu của phú ông.

Ví dụ 2: Tèo chọn đốn đúng một cây [3] để đạt chỉ tiêu của phú ông.

Giới hạn

• Có 30% số test ứng với 30% số điểm của bài có ~𝑛 ≤ 100~.
• Có 30% số test ứng với 30% số điểm của bài có ~100 < 𝑛 ≤ 10^3~.
• Có 40% số test ứng với 40% số điểm của bài có ~10^3 < 𝑛 ≤ 10^5~.

Yêu cầu:

Xâu Palindrome (hay còn gọi là xâu đối xứng) là một chuỗi ký tự có tính chất: đọc từ trái sang phải và từ phải sang trái đều giống nhau. Xâu có 1 ký tự cũng được xem là xâu Palindrome. Xâu con của xâu S là một dãy các ký tự liên tiếp trong xâu S.

Phép chia Palind trên xâu S là một cách chia xâu S thành các xâu con liên tiếp. Trong đó, từng xâu con trong cách chia đó đều là xâu Palindrome.

Cho xâu S, hãy xác định số cách chia Palind có thể thực hiện trên xâu S.

Dữ liệu:

Dòng duy nhất ghi xâu S (không rỗng) chỉ gồm các ký tự chữ cái thường ~'a'..'z'~. Số lượng ký tự của S không quá ~16~ ký tự.

Kết quả:

Một dòng duy nhất ghi số lượng phép chia Palind có thể thực hiện trên xâu S.

Input 1:

aab

Output 1:

2

Input 2:

a

Output 2:

1

Input 3:

banana

Output 3:

5

Giải thích:

Ví dụ 1: S= ~aab~ có thể thực hiện được 2 phép chia Palind như sau: [aa][b] và [a][a][b]

Giới hạn

• 30% số điểm có độ dài xâu không vượt quá ~10~ ký tự.
• 60% số điểm không ràng buộc gì thêm.

Yêu cầu:

An thích nghe nhạc và chỉ có ~k~ phút rảnh. An có danh sách ~n~ bài hát, mỗi bài có độ dài là ~m_i~ phút. An phải nghe hết một bài hát trước khi nghe bài tiếp theo

Hãy tìm một dãy liên tiếp các bài hát sao cho số lượng bài hát là nhiều nhất có thể và An phải đủ thời gian để nghe hết toàn bộ các bài hát này

Dữ liệu:

• Dòng đầu tiên chứ hai số nguyên lần lượt là ~n~ và ~k~ (~1 \leq n \leq 10^5~;~1 \leq k \leq 10^9 ~).
• Dòng tiếp theo chứa ~n~ số nguyên dương ~m_i~ (~1 \leq m_i \leq 10^4~).

Kết quả:

In ra một số nguyên là số lượng bài hát đối ta mà An có thể nghe

Ràng buộc

• 60% số test ~n \leq 10^3~.
• 40% số test ~n \leq 10^5~.

Input:

5 20
9 3 5 4 7

Output:

4

Giải thích

• Dãy hợp lệ là 3 5 4 7.

Yêu cầu:

Tín là một nhà thám hiểm không gian. Sắp đến cậu ấy sẽ tham gia một cuộc thi nhằm tìm kiếm những người cho chuyến du hành không gian 2022 của ASAN. Vì biết đây là một cơ hội ngàn năm có một, Tín không ngừng học hỏi để cải thiện bản thân. Tuy nhiên cậu ấy lại đang phải đối mặt với một vấn đề khó chưa tìm ra lời giải, bạn là người bạn thân của anh ấy và cố gắng giúp Tín giải quyết vấn đề đấy. Mô tả vấn đề như sau:
Tín được cho một dãy số nguyên ~a_1, a_2, ..., a_N~ . Ta định nghĩa độ đẹp của một dãy là số dãy con liên tiếp nhiều nhất có thể trong cách chọn từ dãy đấy các dãy con liên tiếp không giao nhau sao cho tổng của mỗi dãy con đều bằng 0. Cho Q cặp số ~(L_i, R_i)~, Tín được yêu cầu với mỗi cặp số tìm độ đẹp của dãy con liên tiếp ~a_{L_i}, a_{L_{i+1}}, ..., a_{R_i}~ tương ứng.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên N (~1 ≤ N ≤ 4 × 10^5~). • Dòng thứ hai chứa N số nguyên ~a_1, a_2, ..., a_N (|a_i| ≤ 10^9)~. • Dòng thứ ba chứa số nguyên Q (~1 ≤ Q ≤ 4 × 10^5~). • Q dòng tiếp theo mỗi dòng chứa hai số nguyên ~L_i~ và ~R_i~ (~1 ≤ L_i ≤ R_i ≤ N~).

Kết quả:

Ghi ra trên Q dòng, dòng thứ i là độ đẹp của dãy con liên tiếp ~a_{L_i}, a_{L_{i+1}}, ..., a_{R_i}~ tương ứng.

Ví dụ:

Input:

10
1 2 -3 0 1 -4 3 2 -1 1
3
1 10
1 5
2 9

Output:

4
2
2

Giải thích:

Trong dãy con liên tiếp ~a_1, a_2, ..., a_{10}~ ta chọn 4 dãy con liên tiếp không giao nhau gồm các chỉ số {1, 2, 3}, {4}, {5, 6, 7}, {9, 10}.
Trong dãy con liên tiếp ~a_1, a_2, ..., a_5~ ta chọn 2 dãy con liên tiếp không giao nhau gồm các chỉ số {1, 2, 3}, {4}.

Giới hạn:

• Subtask 1 (30%): ~1 ≤ N, Q ≤ 5000~. • Subtask 2 (40%): ~1 ≤ N, Q ≤ 10^5~. • Subtask 3 (30%): Không có giới hạn gì thêm.