Ôn tập

Có \(n\) cây tre được đánh số từ \(1\) đến \(n\) (theo thứ tự từ trái sang phải). Cây tre thứ \(i\) có chiều cao là \(h_i\). Và ở trên mỗi cây tre đều có một quả chuối.

Có một chú khỉ tên là Lucii muốn ăn hết tất cả các quả chuối ở trên tất cả các cây.

Bây giờ chú khỉ đó đang đứng ở gốc của cây tre thứ \(1\). Và trong một giây, chú khỉ đó chỉ có thể thực hiện được một trong các hành động sau :

• Đi lên trên hoặc xuống dưới một đơn vị trên một cây tre

• Ăn quả chuối trên đỉnh của cây tre hiện tại

• Nhảy sang cây tre kế tiếp. Tức là, nếu Lucii đang ở độ cao \(q\) của cây thứ \(i(1\le i\le n-1)\), cô ta sẽ nhảy sang độ cao \(q\) của cây thứ \(i+1\). Hành động này chỉ xảy ra khi \(q>h_{i+1}\)

Nhiệm vụ của bạn là tính thời gian tối thiểu (bằng giây) để chú khỉ ăn hết tất cả các quả chuối.

Input

• Dòng thứ nhất chứa số nguyên \(n(1\le n\le 10^5)\)

• \(n\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(h_i(1\le h_i\le 10^4)\)

Output

• Thời gian tối thiểu cần tìm

Example

2
6 3

12

Cho dãy \(a\) gồm \(8\) số nguyên có giá trị từ \(1\) đến \(8\). Có 2 phép biến đổi trên dãy số này: Phép quay trái \(L\) và phép quay phải \(R\).

Phép biến đổi L là dời số trong dãy từ phải sang trái, số đầu dãy chuyển đến vị trí cuối dãy.

Ví dụ: Dãy \(a: 12345678\) Trạng thái dãy sau khi biến đổi L \(\rightarrow 23456781\).

Tương tự, phép biến đổi R dời số trong dãy từ trái sang phải, số cuối dày chuyển đên vị trí đầu dãy.

Ví dụ: Dãy \(a: 12345678\) Trạng thái dãy sau khi biến đổi R \(\rightarrow 81234567\).

Yêu cầu: Cho một dãy các phép biến đổi, sau khi thực hiện tuần tự các biển đổi đã cho, dãy \(A\) có trạng thái mới, biến đổi thành dãy \(B\). Hãy lập trình xác định dãy \(B\).

Input

• Chỉ gồm \(1\) hàng gồm các kí tự L, R viết liền nhau, dùng để biểu diễn dãy tuần tự các phép biến đổi cho trước. Chiều dài không quá \(200\) kí tự.

Output

• Ghi ra \(1\) dòng biểu diễn dãy \(B\) với các số viết liền nhau.

Example

RRRRRRR

23456781

Bạn được cho 4 số nguyên dương \(x\), \(y\), \(n\) ,\(m\). Hãy tính tính phần dư của giá trị \((x^n - y^n)\) khi chia cho \(m\)

Input

• Dòng đầu tiền : 4 số nguyên dương \(x, y, n, m\) \((x,y,n,m \leq 10^{18})\)

Output

• Phần dư của giá trị \((x^n - y^n)\) khi chia cho \(m\)

3 2 4 3

2

Cho một mảng gồm \(n\) số nguyên dương \(a_{1}, a_{2}, a_{3},..., a_{n}\). Hỏi có bao nhiêu cặp số \(i < j\) và \(a_{i} = a_{j}\).

Lưu ý: Số lượng này có thể rất lớn nên sử dụng kiểu long long.

Input

• Dòng thứ nhất là chiều dài \(n\) của mảng \((1 \leq n \leq 10^{5})\)
• Dòng thứ hai gồm \(n\) số nguyên \(a_{1}, a_{2}, a_{3},..., a_{n}\) \((1 \leq a_{i} \leq 10^{5})\), mỗi số cách nhau một khoảng trắng.

Output

• Gồm 1 dòng duy nhất là số nguyên xác định số lượng các cặp bằng nhau.

Example

5
8 2 9 8 1  

1

7
6 2 4 2 4 3 4

4

Cho dãy gồm \(n\) số nguyên dương và một số nguyên \(K\). Bạn hãy giúp Tèo tìm ra đoạn con dài nhất gồm các phần tử liên tiếp sao cho tổng các phần tử này chia hết cho \(K\).

Input

• Dòng \(1\) là \(N\) và \(K\) \((1 \le n, k \le 10^5)\)
• Dòng thứ \(2\) chứa dãy số \(n\) phần tử \((0 \le A_i \le 10^9)\)

Output

• Là độ dài lớn nhất tìm được.

Example

9 4
3 9 9 5 1 1 10 3 5

6