8739번 - Domino 다국어

Jaś układa domino. Nie robi tego jednak w tradycyjny sposób, tylko bawi się w przewracanie kolejnych klocków domina. Wiemy, że klocki Jasia są różnych wysokości. Jaś postawił n klocków domina w ciągu w taki sposób, aby przewrócenie się dowolnego klocka spowodowało przewrócenie się kolejnego klocka w ciągu. Wiadomo, że kolejny klocek przewróci się, jeśli wysokość przewracanego klocka jest większa od odległości pomiędzy nimi. Jaś chciałby wiedzieć, ile niepotrzebnych klocków może usunąć z ciągu, aby przewrócenie pierwszego klocka w ciągu spowodowało (poprzez przewracanie się pośrednich klocków) przewrócenie się ostatniego klocka w ciągu. Jaś nie może zmieniać położenia klocków.

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą n (1 ≤ n ≤ 10⁶), oznaczającą liczbę klocków Jasia. Drugi wiersz wejścia zawiera ciąg n liczb całkowitych w₁, w₂, ..., w_n (1 ≤ w_i ≤ 10⁹), gdzie w_i oznacza wysokość i - tego klocka w ciągu. Trzeci wiersz wejścia zawiera odległości pomiędzy klockami w ciągu. Składa się z ciągu n - 1 liczb całkowitych x₁, x₂, ..., x_n-1 (1 ≤ x_i ≤ 10⁹), gdzie x_i oznacza odległość pomiędzy i - tym a i + 1 - wszym klockiem w ciągu.

Pierwszy i jedyny wiesz standardowego wyjścia powinien zawierać jedną liczbę całkowitą równą maksymalnej liczbie klocków, które możemy usunąć z ciągu.