C. Hills

Statement

Welcome to Innopolis city. Throughout the whole year, Innopolis citizens suffer from everlasting city construction.

From the window in your room, you see the sequence of n hills, where i-th of them has height ai. The Innopolis administration wants to build some houses on the hills. However, for the sake of city appearance, a house can be only built on the hill, which is strictly higher than neighbouring hills (if they are present). For example, if the sequence of heights is 5, 4, 6, 2, then houses could be built on hills with heights 5 and 6 only.

The Innopolis administration has an excavator, that can decrease the height of an arbitrary hill by one in one hour. The excavator can only work on one hill at a time. It is allowed to decrease hills up to zero height, or even to negative values. Increasing height of any hill is impossible. The city administration wants to build k houses, so there must be at least k hills that satisfy the condition above. What is the minimum time required to adjust the hills to achieve the administration’s plan?

However, the exact value of k is not yet determined, so could you please calculate answers for all k in range ? Here denotes n divided by two, rounded up.

I/O

Input

The first line of input contains the only integer n (1 ≤ n ≤ 5000)—the number of the hills in the sequence.

Second line contains n integers ai (1 ≤ ai ≤ 100 000)—the heights of the hills in the sequence.

Output

Print exactly numbers separated by spaces. The i-th printed number should be equal to the minimum number of hours required to level hills so it becomes possible to build i houses.

Sample

Input

Output

Note

In the first example, to get at least one hill suitable for construction, one can decrease the second hill by one in one hour, then the sequence of heights becomes 1, 0, 1, 1, 1 and the first hill becomes suitable for construction.

In the first example, to get at least two or at least three suitable hills, one can decrease the second and the fourth hills, then the sequence of heights becomes 1, 0, 1, 0, 1, and hills 1, 3, 5 become suitable for construction.

Idea

首先,我们可以预处理出对于每个 hill,要使得它满足条件需要在左边和右边分别付出的代价 $l_i,r_i$。

然后我们可以 $O(n^2)$ DP。设 $f[i][j][k]$ 为考虑前 $i$ 个 hill,$j$ 个 hill 满足条件,第 $i$ 个 hill 的使用情况为 $k$。 显然 $k$ 只有 0 或 1 两种可能。

然后考虑转移方程。对于 $f[i][j][0]$,它可以直接由左边的 hill 的状态转移过来,因为在计算上个状态的时候,已经考虑了 $i$ 对它的影响。显然,有 $f[i][j][0]=min(f[i-1][j][0],f[i-1][j][1])$。

对于 $f[i][j][1]$,我们知道左边的 hill 一定没有使用,可以直接由 $f[i-1][j-1][0]+l[i]+r[i]$ 转移过来。

如果你只写了这个,你就 Gay Gay 了。为什么呢?

我们知道 $f[i-1][j-1][0]=min(f[i-2][j-1][0],f[i-2][j-1][1])$,而 $f[i-2][j-1][1]$ 之中可能已经考虑了 $i-1$ 的高度的影响。这个时候你再无脑加上 $l[i]$ 就可能影响答案。

解决方案是再考虑一下这个值:$f[i-2][j-1][1]+max(0,a[i-2]-a[i])+r[i]$。这样可以规避可能的重复计算,保证答案的正确性。

Code

D. AB-Strings

Statement

There are two strings s and t, consisting only of letters a and b. You can make the following operation several times: choose a prefix of s, a prefix of t and swap them. Prefixes can be empty, also a prefix can coincide with a whole string.

Your task is to find a sequence of operations after which one of the strings consists only of a letters and the other consists only of b letters. The number of operations should be minimized.

I/O

Input

The first line contains a string $s$ ($1 ≤ |s| ≤ 2·10^5$).

The second line contains a string $t$ ($1 ≤ |t| ≤ 2·10^5$).

Here $|s|$ and $|t|$ denote the lengths of $s$and $t$, respectively. It is guaranteed that at least one of the strings contains at least one $a$ letter and at least one of the strings contains at least one $b$ letter.

Output

The first line should contain a single integer $n$ ($0 ≤ n ≤ 5·10^5$) — the number of operations.

Each of the next $n$ lines should contain two space-separated integers $a_i$, $b_i$ — the lengths of prefixes of $s$ and $t$ to swap, respectively.

If there are multiple possible solutions, you can print any of them. It’s guaranteed that a solution with given constraints exists.

Sample

Input

Output

Note

In the first example, you can solve the problem in two operations:

  1. Swap the prefix of the first string with length 1 and the prefix of the second string with length 0. After this swap, you’ll have strings ab and bbb.
  2. Swap the prefix of the first string with length 1 and the prefix of the second string with length 3. After this swap, you’ll have strings bbbb and a.

Idea

Code