113 lines
2.3 KiB
Java
113 lines
2.3 KiB
Java
package chelper;
|
|
|
|
import java.util.Objects;
|
|
import java.util.SortedMap;
|
|
import java.util.TreeMap;
|
|
import java.util.TreeSet;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
import misc.SimpleSavingChelperSolution;
|
|
|
|
|
|
public class TaskC extends SimpleSavingChelperSolution {
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
wrapSolve(testNumber, in, out);
|
|
}
|
|
|
|
class Pos implements Comparable<Pos> {
|
|
long height;
|
|
int pos;
|
|
|
|
public Pos(long height, int pos) {
|
|
this.height = height;
|
|
this.pos = pos;
|
|
}
|
|
|
|
@Override
|
|
public int compareTo(Pos o) {
|
|
int t = Long.compare(height, o.height);
|
|
if (t != 0) {
|
|
return t;
|
|
}
|
|
return -Integer.compare(pos, o.pos);
|
|
}
|
|
|
|
@Override
|
|
public boolean equals(Object o) {
|
|
if (this == o) return true;
|
|
if (o == null || getClass() != o.getClass()) return false;
|
|
Pos pos1 = (Pos) o;
|
|
return height == pos1.height &&
|
|
pos == pos1.pos;
|
|
}
|
|
|
|
@Override
|
|
public int hashCode() {
|
|
|
|
return Objects.hash(height, pos);
|
|
}
|
|
}
|
|
|
|
@Override
|
|
public void solve(int testNumber) {
|
|
int n = in.nextInt();
|
|
|
|
long[] above = in.nextLongArray(n);
|
|
|
|
long[] total = new long[n];
|
|
|
|
TreeSet<Pos> poses = new TreeSet<>();
|
|
for (int i = 0; i < n; i++) {
|
|
poses.add(new Pos(above[i], i));
|
|
}
|
|
// poses.add(new Pos(-1, -1));
|
|
|
|
Pos highest = poses.pollLast();
|
|
total[highest.pos] = highest.height;
|
|
|
|
// while (!poses.isEmpty()) {
|
|
// Pos next = poses.pollLast();
|
|
// if (next.pos > highest.pos) {
|
|
// continue;
|
|
// }
|
|
//
|
|
// long h = highest.height;
|
|
//
|
|
// for (int i = highest.pos; i >= Math.max(next.pos, 0); i--) {
|
|
// total[i] = h;
|
|
// if (h > next.height) {
|
|
// h--;
|
|
// }
|
|
// }
|
|
//
|
|
// highest = next;
|
|
// }
|
|
|
|
long h = highest.height;
|
|
for (int pos = highest.pos; pos < n; pos++) {
|
|
poses.remove(new Pos(above[pos], pos));
|
|
total[pos] = h;
|
|
}
|
|
|
|
for (int pos = highest.pos - 1; pos >= 0; pos--) {
|
|
if (h > poses.last().height) {
|
|
h--;
|
|
}
|
|
total[pos] = h;
|
|
poses.remove(new Pos(above[pos], pos));
|
|
}
|
|
|
|
h = 0;
|
|
long sum = 0;
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
// h = Math.max(h, total[i]);
|
|
sum += total[i] - above[i];
|
|
}
|
|
|
|
out.println(sum);
|
|
}
|
|
}
|