Robot trên lưới

Một robot di chuyển trên lưới nguyên vô hạn, chỉ đi dọc theo các đường lưới.

Người ta đưa cho robot một dãy $m$ điểm nguyên $p_1,p_2,\dots ,p_m$. Gọi $p_0$ là vị trí xuất phát của robot. Robot lần lượt đi từ $p_0$ đến $p_1$, rồi từ $p_1$ đến $p_2$, ..., cho đến $p_m$. Ở mỗi chặng, robot chọn một đường đi ngắn nhất bất kỳ giữa hai điểm liên tiếp (vì chỉ đi theo đường lưới nên có thể có nhiều đường đi ngắn nhất cùng độ dài). Các điểm trong dãy có thể trùng nhau, khi đó robot ghé qua điểm đó đúng số lần nó xuất hiện.

Dãy điểm nay đã bị mất, nhưng robot còn lưu lại nhật ký các bước đi đơn vị của mình: một xâu gồm $n$ ký tự trong $\{L,R,U,D\}$, ký tự thứ $k$ cho biết hướng của bước đi đơn vị thứ $k$ (L: sang trái, R: sang phải, U: lên trên, D: xuống dưới).

Hãy tìm độ dài $m$ nhỏ nhất có thể của dãy điểm.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương $n$ là số bước đi đơn vị mà robot đã thực hiện.
• Dòng thứ hai chứa nhật ký di chuyển: xâu gồm $n$ ký tự, mỗi ký tự thuộc $\{L,R,U,D\}$.

Dữ liệu ra

Một số nguyên duy nhất: độ dài nhỏ nhất có thể của dãy điểm.

Ràng buộc

• $1\le n\le 2·{10}^5$

Ví dụ