import java.util.*; class Main { static final long I=1L<<50; public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n=Integer.parseInt(scan.next()); long p=Integer.parseInt(scan.next()); long[] h=new long[n]; for(int i=0;i=0;--i) r[i]=r[i+1]+Math.max(h[i]-h[i+1],0); MaxSegmentTree s1=new MaxSegmentTree(); MaxSegmentTree s2=new MaxSegmentTree(); long[] dp=new long[n]; dp[0]=0; s1.update(0,l[0]); s2.update(0,-r[0]); for(int i=1;i 0) { x = (x - 1) / 2; this.seg[x] = Math.max(this.seg[2 * x + 1], this.seg[2 * x + 2]); } } long query(int l, int r) { l += SIZE - 1; r += SIZE - 1; long y = -INFINITY; while (l < r) { if ((l & 1) == 0) { y = Math.max(y, this.seg[l]); } if ((r & 1) == 0) { y = Math.max(y, this.seg[r - 1]); } l /= 2; r = (r - 1) / 2; } return y; } }