Có \(N\) khối lập phương được xếp chồng lên nhau trên bàn.

Bạn được cho một chuỗi \(S\) có độ dài \(N\). Màu của khối thứ \(i\) tính từ dưới lên là đỏ nếu ký tự thứ \(i\) trong \(S\) là '0', và là xanh nếu ký tự đó là '1'.

Bạn có thể thực hiện thao tác sau bất kỳ số lần nào: chọn một khối màu đỏ và một khối màu xanh liền kề nhau và loại bỏ chúng. Tại đây, các khối được xếp trên các khối đã loại bỏ sẽ rơi xuống vật thể phía dưới chúng.

Số khối lớn nhất có thể được loại bỏ là bao nhiêu?

Ràng buộc

• \(1 \leq N \leq 10^5\)
• \(|S| = N\)
• Mỗi ký tự trong \(S\) là '0' hoặc '1'.

INPUT FORMAT

• Đầu vào được cung cấp từ Standard Input theo định dạng sau:

  S

OUTPUT FORMAT

• In ra số lượng khối tối đa có thể được loại bỏ.

Ví dụ:

Input

0011

Output

4

Tất cả bốn khối có thể được loại bỏ, bằng cách thực hiện các thao tác như sau:

Loại bỏ khối thứ hai và thứ ba từ dưới lên. Sau đó, khối thứ tư rơi xuống khối đầu tiên.

Loại bỏ khối đầu tiên và thứ hai từ dưới lên.

Input

11011010001011

Output

12

Giải thích ví dụ mẫu

Ví dụ 1:

• Input:

  0011

• Giải thích:

  • Tất cả bốn khối có thể được loại bỏ bằng cách loại bỏ từng cặp khối đỏ và xanh liền kề.

Ví dụ 2:

• Input:

  11011010001011

• Giải thích:

  • Có 12 khối có thể được loại bỏ bằng cách liên tiếp loại bỏ các cặp khối màu đỏ và xanh.
    

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House