I. Inner Product
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a sequence of positive integers $$$a_1, a_2, \dots, a_n$$$ and a string $$$s$$$ of length $$$n - 1$$$.

For each $$$i$$$ from $$$1$$$ to $$$n - 1$$$:

  • if $$$s_i \text{ is equal to } \lt $$$, then $$$b_i \lt b_{i + 1}$$$;
  • if $$$s_i \text{ is equal to } =$$$, then $$$b_i = b_{i + 1}$$$;
  • if $$$s_i \text{ is equal to } \gt $$$, then $$$b_i \gt b_{i + 1}$$$.

Your task is to choose a sequence of positive integers $$$b_1, b_2, \dots, b_n$$$ satisfying all these relations.

Among all valid sequences, minimize

$$$$$$a_1 b_1 + a_2 b_2 + \dots + a_n b_n.$$$$$$

For the given constraints, it can be proved that the optimal sequence is unique.

Input

The first line contains one integer $$$n$$$ ($$$2 \le n \le 200'000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 1'000'000$$$).

The third line contains a string $$$s$$$ of length $$$n - 1$$$, consisting only of the characters <, =, and >.

Output

Print the minimum possible value of

$$$$$$a_1 b_1 + a_2 b_2 + \dots + a_n b_n$$$$$$

in the first line.

In the second line, print the unique optimal sequence $$$b_1, b_2, \dots, b_n$$$.

It can be proved that, for the given constraints, the minimum value always fits in a signed $$$64$$$-bit integer.

Examples
Input
6
3 1 4 1 5 9
<=>><
Output
43
1 3 3 2 1 2
Input
2
2 7
<
Output
16
1 2
Input
8
8 2 2 8 3 7 4 6
=<<=>>=
Output
71
1 1 2 3 3 2 1 1
Note

The first sample requires

$$$$$$b_1 \lt b_2 = b_3 \gt b_4 \gt b_5 \lt b_6.$$$$$$

The sequence $$$1\ 3\ 3\ 2\ 1\ 2$$$ satisfies all relations, and its cost is

$$$$$$3 \cdot 1 + 1 \cdot 3 + 4 \cdot 3 + 1 \cdot 2 + 5 \cdot 1 + 9 \cdot 2 = 43.$$$$$$