Trên một con đường có ~n~ toà nhà. Mỗi toà nhà được sơn bằng một màu Đỏ, Vàng, Xanh hoặc Tím. Người ta muốn sơn lại một số toà nhà (bằng một trong các màu Đỏ, Vàng, Xanh, Tím) sao cho không có hai toà nhà liên tiếp có cùng màu sơn.

Yêu cầu: Tìm số nhà cần sơn lại ít nhất.

Input

• Dòng đầu tiên chứ số nguyên dương ~n (1 \le n \le 10^5)~;
• Dòng thứ hai chứa ~n~ ký tự, mỗi ký tự đại diện cho một toà nhà thuộc một trong ba loại D, V, X.

Output

Ghi ra số lượng nhà cần sơn lại ít nhất

Ví dụ

Sample Input

14
VVXDDDTXVTXDVX

Sample Output

2

Cho dãy số nguyên dương ~a_1, a_2, ..., a_n~. Dãy số ~a_i, a_{i+1}, ..., a_j~ thoả mãn ~a_i \le a_{i+1} \le ... \le a_j~, với được gọi là dãy con không giảm của dãy số đã cho và khi đó số ~j-i+1~ được gọi là độ dài của dãy.

Cho dãy số ~u~ xác định bởi: ~u_1 = 1; u_2 = 3; U_k = U_{k-1} + k (k \ge 3)~

Yêu cầu: Trong số các dãy con không giảm của dãy số đã cho mà các phần tử của nó đều thuộc dãy số ~u~. Hãy tìm dãy con có độ dài lớn nhất.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n (n \le 10^5)~
• Dòng thứ hai chứa n số nguyên dương ~a_i (a_i \le 10^8)~ mô tả dãy số

Output

Ghi ra số nguyên ~d~ là độ dài của dãy con không giảm tìm được (quy ước rằng nếu không có dãy con nào thoả mãn điều kiện đặt ra thì ~d = 0~)

Ví dụ

Sample Input

8
2 2007 6 6 15 16 3 21

Sample Output

3

Cho dãy A gồm n số nguyên ~a_1, a_2, ..., a_n~.

Yêu cầu: Tìm độ dài dãy con liên tiếp dài nhất mà các phần tử âm dương xen kẽ.

Input

• Dòng đầu tiên chứa số n ~(n \le 10^5)~
• Dòng thứ hai chứa ~n~ phần tử của dãy A có giá trị tuyệt đối không vượt quá ~10^9~

Output

Ghi ra số lượng dãy con dài nhất và độ dài dãy con tìm được

Ví dụ

Sample Input

10
1 -5 2 0 -6 2 -9 -5 3 7

Sample Output

2 3

Giải thích

Dãy con đan dấu có độ dài dài nhất là 3. Có 2 dãy con độ dài 3 là 1, -5, 2 và -6, 2, -9

Cho dãy A gồm n số nguyên ~a_1, a_2, .. a_n~

Yêu cầu: Tìm độ dài dãy con liên tiếp dài nhất, mà các phàn tử gồm toàn số nguyên tố.

Input

• Dòng đầu tiên chứa số ~n (n \le 10^4)~
• Dòng thứ hai chứa n phần tử của dãy A có giá trị tuyệt đối không vượt quá ~10^9~

Output

Ghi ra số lượng dãy con dài nhất và độ dài dãy con tìm được

Ví dụ

Sample Input

10
12 11 7 3 8 8 17 29 2 1

Sample Output

2 3