### PROBLEM LINK:

**Author:** Dmytro Berezin

**Primary Tester:** Misha Chorniy

**Editorialist:** Hussain Kara Fallah

### DIFFICULTY:

Cakewalk

### PREREQUISITES:

None

### PROBLEM:

Given a sequence of **N** arithmetic signs **( = , + , - )** between **N+1** unknown integers. You are allowed to fix these integers using numbers in the range [1,P] such that the expression is true when you read it from left to right. (Numbers don’t violate the signs). You are asked to calculate **minimum** possible **P** such you can construct a valid expression.

### EXPLANATION:

First of all, it’s clear that we can drop all **‘=’** signs and pretend that they never existed, because each number which follows an ‘=’ sign would be identical to the number preceding this sign. So these signs aren’t affecting our answer at all.

After discarding all ‘=’ signs our answer would be :

**P = max(maximum number of consecutive ‘<’ signs, maximum number of consecutive ‘>’ signs) + 1**

Let’s process our expression from left to right, If we are facing **X (X ≤ P-1)** consecutive ‘<’ signs, our starting number would be **P-X**, and we increment our last number by 1 after each sign,so the number after the last sign would be exactly **P** (which will be followed by ‘>’ sign). Our last number will be followed by **Y** consecutive ‘>’ signs, so we assign the next number to **Y (Y < P)** and we decrement the last number by 1 by each ‘>’ sign we process. The number after the last sign would be **1**. (In case our expression starts with ‘>’ the situation would just be reversed).

After that we would have another block of **Z** consecutive ‘<’ signs, so we assign the next number to **P-Z (P-Z ≥ 1)** so the number after the last sign would be **P** and we continue…

Following this approach, the last number after a block of consecutive ‘<’ signs would be **P** (the maximal value), and the last number after a block of consecutive ‘>’ signs would be **1** (the minimal value). So according to our bold assumption below we can assign values using numbers in the range **[1,P]** without violating the signs.

Let’s take an example:

<<<=>=>=>>><<>>>><<<<<>><<>>

After removing = signs our sequence would be

<<< >>>>> << >>>> << >>>>>

(Blocks are separated by spaces for clarity)

here P = max(3 , 5 , 2 , 4 , 5 , 2 , 2 , 2) + 1 = 6

Our sequence would be

**3** < 4 < 5 < **6** > 5 > 4 > 3 > 2 > **1** < **5** < **6** > **4** > 3 > 2 > **1** < **5** < 6 > 5 > 4 > 3 > 2 > 1

### AUTHOR’S AND TESTER’S SOLUTIONS:

**TESTER’s solution**: Will be found here

**EDITORIALIST’s solution**: Will be found here