結果
| 問題 | No.409 ダイエット |
| ユーザー |
 バイト
|
| 提出日時 | 2018-10-09 20:28:45 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 390 ms / 2,000 ms |
| コード長 | 45,100 bytes |
| コンパイル時間 | 6,381 ms |
| コンパイル使用メモリ | 102,412 KB |
| 実行使用メモリ | 56,508 KB |
| 最終ジャッジ日時 | 2024-10-12 16:45:09 |
| 合計ジャッジ時間 | 23,237 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 51 ms
37,184 KB |
| testcase_01 | AC | 51 ms
37,424 KB |
| testcase_02 | AC | 52 ms
36,952 KB |
| testcase_03 | AC | 53 ms
37,536 KB |
| testcase_04 | AC | 52 ms
37,420 KB |
| testcase_05 | AC | 52 ms
37,480 KB |
| testcase_06 | AC | 52 ms
37,212 KB |
| testcase_07 | AC | 51 ms
37,504 KB |
| testcase_08 | AC | 52 ms
37,464 KB |
| testcase_09 | AC | 53 ms
37,140 KB |
| testcase_10 | AC | 53 ms
37,436 KB |
| testcase_11 | AC | 54 ms
37,468 KB |
| testcase_12 | AC | 53 ms
37,380 KB |
| testcase_13 | AC | 53 ms
37,504 KB |
| testcase_14 | AC | 53 ms
37,456 KB |
| testcase_15 | AC | 53 ms
37,136 KB |
| testcase_16 | AC | 54 ms
37,148 KB |
| testcase_17 | AC | 55 ms
37,244 KB |
| testcase_18 | AC | 52 ms
37,392 KB |
| testcase_19 | AC | 53 ms
36,956 KB |
| testcase_20 | AC | 52 ms
37,496 KB |
| testcase_21 | AC | 52 ms
37,428 KB |
| testcase_22 | AC | 53 ms
37,424 KB |
| testcase_23 | AC | 54 ms
37,008 KB |
| testcase_24 | AC | 53 ms
37,464 KB |
| testcase_25 | AC | 54 ms
37,196 KB |
| testcase_26 | AC | 52 ms
37,376 KB |
| testcase_27 | AC | 52 ms
37,104 KB |
| testcase_28 | AC | 52 ms
37,228 KB |
| testcase_29 | AC | 54 ms
37,180 KB |
| testcase_30 | AC | 54 ms
37,356 KB |
| testcase_31 | AC | 56 ms
37,140 KB |
| testcase_32 | AC | 55 ms
37,232 KB |
| testcase_33 | AC | 54 ms
36,960 KB |
| testcase_34 | AC | 52 ms
37,504 KB |
| testcase_35 | AC | 95 ms
38,888 KB |
| testcase_36 | AC | 86 ms
39,004 KB |
| testcase_37 | AC | 94 ms
39,076 KB |
| testcase_38 | AC | 94 ms
38,820 KB |
| testcase_39 | AC | 94 ms
38,784 KB |
| testcase_40 | AC | 95 ms
38,928 KB |
| testcase_41 | AC | 96 ms
38,720 KB |
| testcase_42 | AC | 96 ms
39,112 KB |
| testcase_43 | AC | 91 ms
38,844 KB |
| testcase_44 | AC | 85 ms
38,716 KB |
| testcase_45 | AC | 94 ms
38,612 KB |
| testcase_46 | AC | 98 ms
39,040 KB |
| testcase_47 | AC | 97 ms
39,032 KB |
| testcase_48 | AC | 96 ms
38,948 KB |
| testcase_49 | AC | 99 ms
38,936 KB |
| testcase_50 | AC | 94 ms
38,940 KB |
| testcase_51 | AC | 96 ms
38,976 KB |
| testcase_52 | AC | 97 ms
39,024 KB |
| testcase_53 | AC | 100 ms
38,976 KB |
| testcase_54 | AC | 95 ms
39,000 KB |
| testcase_55 | AC | 251 ms
47,256 KB |
| testcase_56 | AC | 354 ms
50,848 KB |
| testcase_57 | AC | 342 ms
50,680 KB |
| testcase_58 | AC | 253 ms
46,948 KB |
| testcase_59 | AC | 311 ms
48,124 KB |
| testcase_60 | AC | 229 ms
47,016 KB |
| testcase_61 | AC | 335 ms
50,460 KB |
| testcase_62 | AC | 338 ms
51,004 KB |
| testcase_63 | AC | 345 ms
50,224 KB |
| testcase_64 | AC | 261 ms
47,156 KB |
| testcase_65 | AC | 353 ms
50,436 KB |
| testcase_66 | AC | 352 ms
50,916 KB |
| testcase_67 | AC | 311 ms
49,592 KB |
| testcase_68 | AC | 309 ms
48,192 KB |
| testcase_69 | AC | 340 ms
50,284 KB |
| testcase_70 | AC | 354 ms
52,500 KB |
| testcase_71 | AC | 283 ms
48,624 KB |
| testcase_72 | AC | 385 ms
56,508 KB |
| testcase_73 | AC | 377 ms
54,416 KB |
| testcase_74 | AC | 302 ms
48,836 KB |
| testcase_75 | AC | 387 ms
53,964 KB |
| testcase_76 | AC | 349 ms
52,428 KB |
| testcase_77 | AC | 283 ms
48,308 KB |
| testcase_78 | AC | 299 ms
48,856 KB |
| testcase_79 | AC | 268 ms
48,428 KB |
| testcase_80 | AC | 389 ms
55,808 KB |
| testcase_81 | AC | 390 ms
53,876 KB |
| testcase_82 | AC | 338 ms
52,352 KB |
| testcase_83 | AC | 364 ms
52,836 KB |
| testcase_84 | AC | 325 ms
50,236 KB |
| testcase_85 | AC | 144 ms
41,940 KB |
| testcase_86 | AC | 330 ms
49,248 KB |
| testcase_87 | AC | 378 ms
53,380 KB |
| testcase_88 | AC | 247 ms
46,576 KB |
| testcase_89 | AC | 360 ms
52,608 KB |
| testcase_90 | AC | 243 ms
46,524 KB |
| testcase_91 | AC | 355 ms
52,944 KB |
ソースコード
import java.io.*;
import static java.lang.Math.*;
import static java.lang.Math.min;
import java.math.BigDecimal;
import java.util.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import java.util.stream.*;
/**
* @author baito
*/
@SuppressWarnings("unchecked")
public class Main {
static boolean DEBUG = true;
static StringBuilder sb = new StringBuilder();
static int INF = (int) 1e9 + 100;
static int MINF = (int) -1e9 - 100;
static long LINF = (long) 1e18 + 100;
static long MLINF = (long) -1e18 - 100;
static int MOD = (int) 1e9 + 7;
static double EPS = 1e-10;
static int[] y4 = {-1, 1, 0, 0};
static int[] x4 = {0, 0, -1, 1};
static int[] y8 = {0, 1, 0, -1, -1, 1, 1, -1};
static int[] x8 = {1, 0, -1, 0, 1, -1, 1, -1};
static boolean[] isPrime;
static ArrayList<Integer> primes;
static char[][] S;
static long maxRes = Long.MIN_VALUE;
static long minRes = Long.MAX_VALUE;
static long[] fac, finv, inv;
static int N;
static long[] D;
public static void solve() throws Exception {
//longを忘れるなオーバーフローするぞ
N = ni();
long A = ni();
long B = ni();
long W = ni();
D = nla(N);
//i日目に食べた時の最小
long[] dp = new long[N + 1];
// ConvexHullTrick c = new ConvexHullTrick(N + 100, true, false, true);
// for (int i = 1; i < N + 1; i++) {
// dp[i] = c.min(i) + A - A * i + D[i - 1] + B * i * (i - 1) / 2;
// c.add(-B * i, dp[i] + A * i + B * i * (i + 1) / 2);
// }
ConvexHullTrick c = new ConvexHullTrick(N);
c.add(0, 0);
for (int i = 1; i < N + 1; i++) {
long I = i;
dp[i] = c.query(I) + A - A * I + D[i - 1] + B * I * (I - 1) / 2;
c.add(-B * I, dp[i] + A * I + B * I * (I + 1) / 2);
}
for (int i = 0; i < N + 1; i++) {
long I = i;
chMin(W + dp[i] - (N - I) * A + B * (N - I) * (N - I + 1) / 2);
}
System.out.println(minRes);
}
private static class ConvexHullTrick {
LinkedList<Pair> q;
// add における a が単調非増加、query における x が単調非減少である場合
// add O(n), query O(n + q)
ConvexHullTrick(int n) {
q = new LinkedList<>();
}
// ax+b を追加。a は単調非増加とする
private void add(long a, long b) {
Pair next = new Pair(a, b);
while (q.size() >= 2) {
Pair curr = q.get(q.size() - 1);
Pair prev = q.get(q.size() - 2);
if (check(prev, curr, next)) {
break;
}
q.removeLast();
}
q.add(next);
}
// f(x)の最小値。x は単調非減少とする
private long query(long x) {
long fx0 = fx(q.get(0), x);
while (q.size() > 1) {
long fx1 = fx(q.get(1), x);
if (fx0 < fx1) {
return fx0;
}
q.removeFirst();
fx0 = fx1;
}
return fx0;
}
// i 番目の直線を使った時の f(x) の値
private long fx(Pair i, long x) {
return i.a * x + i.b;
}
// curr の直線が必要な場合 true
private boolean check(Pair prev, Pair curr, Pair next) {
return (next.b - curr.b) * (curr.a - prev.a) < (curr.b - prev.b) * (next.a - curr.a);
}
private static class Pair {
long a;
long b;
Pair(long a, long b) {
this.a = a;
this.b = b;
}
}
}
// static class ConvexHullTrick {
// boolean minQuery, angInc, xinc, redBlue;
// long[][] line;
// int tail;
//
// ConvexHullTrick(int maxLine, boolean minQuery, boolean angInc, boolean xinc) {
// line = new long[maxLine][2];
// this.minQuery = minQuery;
// this.angInc = angInc;
// this.xinc = xinc;
// redBlue = minQuery ^ angInc;
// tail = 1;
// }
//
// //ax + b
// void add(long a, long b) {
// line[tail][0] = a;
// line[tail][1] = b;
// tail++;
// while (tail >= 3 && bad(line[tail - 3], line[tail - 2], line[tail - 1])) {
// line[tail - 2][0] = line[tail - 1][0];
// line[tail - 2][1] = line[tail - 1][1];
// tail--;
// }
// }
//
// boolean bad(long[] l1, long[] l2, long[] l3) {
// //最小クエリ 傾き減少
// if (redBlue) {
// return (l3[1] - l2[1]) * (l2[0] - l1[0]) >= (l2[1] - l1[1]) * (l3[0] - l2[0]);
// } else {
// return (l3[1] - l2[1]) * (l2[0] - l1[0]) <= (l2[1] - l1[1]) * (l3[0] - l2[0]);
// }
// }
//
// long f(int lidx, long x) {
// return line[lidx][0] * x + line[lidx][1];
// }
//
// int head = 0;
//
// //xが単調とは限らない
// long min(long x) {
// if (xinc) {
// while (line.length - head >= 2 && f(head, x) >= f(head + 1, x)) {
// head++;
// }
// return f(head, x);
// } else {
// int min = -1;
// int max = tail - 1;
// while (max - min > 1) {
// int med = (max + min) / 2;
// if (f(med, x) >= f(med + 1, x)) {
// min = med;
// } else {
// max = med;
// }
// }
// return f(max, x);
// }
// }
//
//
// long max(long x) {
// if (xinc) {
// while (line.length - head >= 2 && f(head, x) <= f(head + 1, x)) {
// head++;
// }
// return f(head, x);
// } else {
// int min = -1;
// int max = tail - 1;
// while (max - min > 1) {
// int med = (max + min) / 2;
// if (f(med, x) <= f(med + 1, x)) {
// min = med;
// } else {
// max = med;
// }
// }
// return f(max, x);
// }
// }
// }
public static boolean calc(long va) {
//貪欲にギリギリセーフを選んでいく。
int v = (int) va;
return true;
}
//条件を満たす最大値、あるいは最小値を求める
static int mgr(long ok, long ng) {
//int ok = 0; //解が存在する
//int ng = N; //解が存在しない
while (Math.abs(ok - ng) > 1) {
long mid;
if (ok < 0 && ng > 0 || ok > 0 && ng < 0) mid = (ok + ng) / 2;
else mid = ok + (ng - ok) / 2;
if (calc(mid)) {
ok = mid;
} else {
ng = mid;
}
}
if (calc(ok)) return (int) ok;
else return -1;
}
static <T> void initStreamArray(ArrayList<T>[] a, int n) {
a = Stream.generate(ArrayList::new).limit(n).toArray(ArrayList[]::new);
}
//消す候補
static ArrayList<Integer> divisors(int n) {
ArrayList<Integer> res = new ArrayList<>();
for (int i = 1; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
res.add(i);
if (i != n / i) res.add(n / i);
}
}
return res;
}
static ArrayList<Long> divisors(long n) {
ArrayList<Long> res = new ArrayList<>();
for (long i = 1; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
res.add(i);
if (i != n / i) res.add(n / i);
}
}
return res;
}
static ArrayList<Integer> factorization(int n) {
if (primes == null) setPrimes();
ArrayList<Integer> fact = new ArrayList<>();
for (int p : primes) {
if (n % p == 0) fact.add(p);
while (n % p == 0) n /= p;
if (n == 1) break;
}
if (n != 1) fact.add(n);
return fact;
}
boolean equal(double a, double b) {
return a == 0 ? abs(b) < EPS : abs((a - b) / a) < EPS;
}
public static void chMax(long v) {
maxRes = Math.max(maxRes, v);
}
public static void chMin(long v) {
minRes = Math.min(minRes, v);
}
//便利系
public static long[] rui(int[] a) {
long[] res = new long[a.length + 1];
for (int i = 0; i < a.length; i++) {
res[i + 1] = a[i];
}
for (int i = 0; i < a.length; i++) {
res[i + 1] += res[i];
}
return res;
}
//p[i].nowx := i番目に小さいｖの値 p[i].nowy := その個数
//0個の物は除く
public static P[] mato(int[] a) {
CouMap map = new CouMap(a);
P[] res = new P[map.size()];
int i = 0;
for (Map.Entry<Long, Long> m : map.map.entrySet()) {
res[i++] = new P((int) (long) m.getKey(), (int) (long) m.getValue());
}
sort(res);
return res;
}
public static int[] imosu(int[] f, int[] t, int n) {
int[] imosu = new int[n + 1];
for (int i = 0; i < f.length; i++) {
imosu[f[i]]++;
imosu[t[i] + 1]--;
}
for (int i = 0; i < n; i++) {
imosu[i + 1] += imosu[i];
}
return imosu;
}
static int[] inverse(int[] a) {
int[] res = new int[a.length];
for (int i = 0; i < a.length; i++)
res[a[i]] = i;
return res;
}
public static String notE(double v) {
return BigDecimal.valueOf(v).toPlainString();
}
public static <T> void print(ArrayList<T> a) {
for (T t : a) {
System.out.println(t);
}
}
public static void print(int[] a) {
for (int i = 0; i < a.length; i++)
System.out.println(a[i]);
}
public static void print(long[] a) {
for (int i = 0; i < a.length; i++)
System.out.println(a[i]);
}
//bit関連
public static boolean bget(BitSet bit, int keta) {
return bit.nextSetBit(keta) == keta;
}
public static boolean bget(long bit, int keta) {
return ((bit >> keta) & 1) == 1;
}
public static int bget3(long bit, int keta) {
bit /= (long) pow(3, keta);
return (int) (bit % 3);
}
public static int getHashA(long key) {
return (int) (key >> 32);
}
public static int getHashB(long key) {
return (int) (key & -1);
}
//正の数のみ
public static long getHashKey(int a, int b) {
return (long) a << 32 | b;
}
//数学関係--------------------------------
//a/bを返す
public static long ceil(long a, long b) {
return (a % b == 0) ? a / b : a / b + 1;
}
public static double sqrt(double v) {
return Math.sqrt(v);
}
public static long sqrt(long v) {
long res = (long) Math.sqrt(v);
while (res * res > v) res--;
return res;
}
static double[][] PER_DP;
static double ncrPer(int n, int r) {
if (n < r) return 0;
if (PER_DP == null) {
PER_DP = new double[5001][5001];
PER_DP[0][0] = 1;
for (int ni = 0; ni < PER_DP.length - 1; ni++) {
for (int ri = 0; ri < ni + 1; ri++) {
PER_DP[ni + 1][ri] += PER_DP[ni][ri] / 2;
PER_DP[ni + 1][ri + 1] += PER_DP[ni][ri] / 2;
}
}
}
return PER_DP[n][r];
}
//mod関連
public static int mod(long a, int m) {
return (int) ((a % m + m) % m);
}
static void setMod() {
fac = new long[(int) 1e6 + 1000];
finv = new long[(int) 1e6 + 1000];
inv = new long[(int) 1e6 + 1000];
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < 1e6 + 1000; i++) {
fac[i] = mMul(fac[i - 1], i);
inv[i] = MOD - mMul(inv[MOD % i], (MOD / i));
finv[i] = mMul(finv[i - 1], inv[i]);
}
}
static int mNcr(int n, int r) {
if (n < 0 || r < 0 || n < r) return 0;
int result = mMul(fac[n], finv[n - r]);
result = mMul(result, finv[r]);
return result;
}
public static int mSum(long a, long b) {
return (int) (((a % MOD + b % MOD) % MOD + MOD) % MOD);
}
public static int mDiff(long a, long b) {
return mSum(a, -b);
}
public static int mMul(long a, long b) {
return (int) (((a % MOD * b % MOD) % MOD + MOD) % MOD);
}
public static int mDiv(long a, long b) {
return mMul(a, mInv(b));
}
public static long mSums(long... lar) {
long res = 0;
for (long l : lar)
res = (res + l % MOD) % MOD;
return (res + MOD) % MOD;
}
public static long mDiffs(long... lar) {
long res = lar[0] % MOD;
for (int i = 1; i < lar.length; i++) {
res = (res - lar[i] % MOD) % MOD;
}
return (res + MOD) % MOD;
}
public static long mMuls(long... lar) {
long res = 1;
for (long l : lar)
res = (res * (l % MOD)) % MOD;
return (res + MOD) % MOD;
}
public static long mDivs(long... lar) {
long res = lar[0] % MOD;
for (int i = 1; i < lar.length; i++) {
res = mMul(res, mInv(lar[i]));
}
return (res + MOD) % MOD;
}
static long mInv(long n) {
return mPow(n, MOD - 2);
}
static int mPow(long x, long n) {
long res = 1L;
while (n > 0) {
if ((n & 1) == 1) {
res = res * x % MOD;
}
x = x * x % MOD;
n >>= 1;
}
return (int) ((res + MOD) % MOD);
}
//↑nCrをmod計算するために必要
static long lcm(long n, long r) {
return n / gcd(n, r) * r;
}
static int gcd(int n, int r) {
return r == 0 ? n : gcd(r, n % r);
}
static long gcd(long n, long r) {
return r == 0 ? n : gcd(r, n % r);
}
public static int u0(int a) {
if (a < 0) return 0;
return a;
}
public static long u0(long a) {
if (a < 0) return 0;
return a;
}
public static double u0(double a) {
if (a < 0) return 0;
return a;
}
public static boolean[][] tbt(char[][] s, char c) {
boolean[][] res = new boolean[s.length][s[0].length];
for (int hi = 0; hi < s.length; hi++)
for (int wi = 0; wi < s[0].length; wi++)
if (s[hi][wi] == c) res[hi][wi] = true;
return res;
}
public static int[] tia(int a) {
int[] res = new int[keta(a)];
for (int i = res.length - 1; i >= 0; i--) {
res[i] = a % 10;
a /= 10;
}
return res;
}
public static int[][] tit(char[][] a) {
int[][] res = new int[a.length][a[0].length];
for (int hi = 0; hi < a.length; hi++) {
for (int wi = 0; wi < a[0].length; wi++) {
res[hi][wi] = a[hi][wi] - '0';
}
}
return res;
}
public static Integer[] toIntegerArray(int[] ar) {
Integer[] res = new Integer[ar.length];
for (int i = 0; i < ar.length; i++) {
res[i] = ar[i];
}
return res;
}
//k個の次の組み合わせをビットで返す 大きさに上限はない 110110 -> 111001
public static long bitNextComb(long comb) {
long x = comb & -comb; //最下位の1
long y = comb + x; //連続した下の1を繰り上がらせる
return ((comb & ~y) / x >> 1) | y;
}
public static int keta(long num) {
int res = 0;
while (num > 0) {
num /= 10;
res++;
}
return res;
}
public static int ketaSum(long num) {
int res = 0;
while (num > 0) {
res += num % 10;
num /= 10;
}
return res;
}
public static boolean isOutofIndex(int x, int y, int w, int h) {
if (x < 0 || y < 0) return true;
if (w <= x || h <= y) return true;
return false;
}
public static boolean isOutofIndex(int x, int y, char[][] ban) {
if (x < 0 || y < 0) return true;
if (ban[0].length <= x || ban.length <= y) return true;
return false;
}
public static void setPrimes() {
int n = 100001;
isPrime = new boolean[n];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (!isPrime[i]) continue;
for (int j = i * 2; j < n; j += i) {
isPrime[j] = false;
}
}
primes = new ArrayList<>();
for (int i = 2; i < n; i++) {
if (isPrime[i]) primes.add(i);
}
}
public static void revSort(int[] a) {
Arrays.sort(a);
reverse(a);
}
public static void revSort(long[] a) {
Arrays.sort(a);
reverse(a);
}
public static P[] clone(P[] ar) {
P[] res = new P[ar.length];
for (int i = 0; i < ar.length; i++) {
res[i] = new P(ar[i].x, ar[i].y);
}
return res;
}
public static int[][] clone(int[][] ar) {
int[][] nr = new int[ar.length][ar[0].length];
for (int i = 0; i < ar.length; i++)
nr[i] = ar[i].clone();
return nr;
}
public static long[][] clone(long[][] ar) {
long[][] nr = new long[ar.length][ar[0].length];
for (int i = 0; i < ar.length; i++)
nr[i] = ar[i].clone();
return nr;
}
public static double[][] clone(double[][] ar) {
double[][] nr = new double[ar.length][ar[0].length];
for (int i = 0; i < ar.length; i++)
nr[i] = ar[i].clone();
return nr;
}
public static boolean[][] clone(boolean[][] ar) {
boolean[][] nr = new boolean[ar.length][ar[0].length];
for (int i = 0; i < ar.length; i++)
nr[i] = ar[i].clone();
return nr;
}
public static char[][] clone(char[][] ar) {
char[][] nr = new char[ar.length][ar[0].length];
for (int i = 0; i < ar.length; i++)
nr[i] = ar[i].clone();
return nr;
}
public static int[][][] clone(int[][][] ar) {
int[][][] nr = new int[ar.length][ar[0].length][ar[0][0].length];
for (int i = 0; i < ar.length; i++)
nr[i] = clone(ar[i]);
return nr;
}
public static long[][][] clone(long[][][] ar) {
long[][][] nr = new long[ar.length][ar[0].length][ar[0][0].length];
for (int i = 0; i < ar.length; i++)
nr[i] = clone(ar[i]);
return nr;
}
public static double[][][] clone(double[][][] ar) {
double[][][] nr = new double[ar.length][ar[0].length][ar[0][0].length];
for (int i = 0; i < ar.length; i++)
nr[i] = clone(ar[i]);
return nr;
}
public static boolean[][][] clone(boolean[][][] ar) {
boolean[][][] nr = new boolean[ar.length][ar[0].length][ar[0][0].length];
for (int i = 0; i < ar.length; i++)
nr[i] = clone(ar[i]);
return nr;
}
public static char[][][] clone(char[][][] ar) {
char[][][] nr = new char[ar.length][ar[0].length][ar[0][0].length];
for (int i = 0; i < ar.length; i++)
nr[i] = clone(ar[i]);
return nr;
}
/**
* <h1>指定した値以上の先頭のインデクスを返す</h1>
* <p>配列要素が０のときは、０が返る。</p>
*
* @return<b>int</b> ： 探索した値以上で、先頭になるインデクス
* 値が無ければ、挿入できる最小のインデックス
*/
public static <T extends Number> int lowerBound(final List<T> lis, final T value) {
int low = 0;
int high = lis.size();
int mid;
while (low < high) {
mid = ((high - low) >>> 1) + low; //(low + high) / 2 (オーバーフロー対策)
if (lis.get(mid).doubleValue() < value.doubleValue()) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
//v未満で最大のiを返す。ただしv以上を満たすiがあるなら最小のiを返す
public static <T extends Number> int rlowerBound(final List<T> lis, final T value) {
int ind = lowerBound(lis, value);
if (ind == lis.size() || !lis.get(ind).equals(value)) ind--;
return ind;
}
/**
* <h1>指定した値より大きい先頭のインデクスを返す</h1>
* <p>配列要素が０のときは、０が返る。</p>
*
* @return<b>int</b> ： 探索した値より上で、先頭になるインデクス
* 値が無ければ、挿入できる最小のインデックス
*/
public static <T extends Number> int upperBound(final List<T> lis, final T value) {
int low = 0;
int high = lis.size();
int mid;
while (low < high) {
mid = ((high - low) >>> 1) + low; //(low + high) / 2 (オーバーフロー対策)
if (lis.get(mid).doubleValue() < value.doubleValue()) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
public static int lowerBound(final int[] arr, final int value) {
int low = 0;
int high = arr.length;
int mid;
while (low < high) {
mid = ((high - low) >>> 1) + low; //(low + high) / 2 (オーバーフロー対策)
if (arr[mid] < value) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
public static int rlowerBound(final int[] arr, final int value) {
int ind = lowerBound(arr, value);
if (ind == arr.length || arr[ind] != value) ind--;
return ind;
}
public static int upperBound(final int[] arr, final int value) {
int low = 0;
int high = arr.length;
int mid;
while (low < high) {
mid = ((high - low) >>> 1) + low; //(low + high) / 2 (オーバーフロー対策)
if (arr[mid] <= value) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
public static int lowerBound(final long[] arr, final long value) {
int low = 0;
int high = arr.length;
int mid;
while (low < high) {
mid = ((high - low) >>> 1) + low; //(low + high) / 2 (オーバーフロー対策)
if (arr[mid] < value) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
public static int rlowerBound(final long[] arr, final long value) {
int ind = lowerBound(arr, value);
if (ind == arr.length || arr[ind] != value) ind--;
return ind;
}
public static int upperBound(final long[] arr, final long value) {
int low = 0;
int high = arr.length;
int mid;
while (low < high) {
mid = ((high - low) >>> 1) + low; //(low + high) / 2 (オーバーフロー対策)
if (arr[mid] <= value) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
//次の順列に書き換える、最大値ならfalseを返す
public static boolean nextPermutation(int A[]) {
int len = A.length;
int pos = len - 2;
for (; pos >= 0; pos--) {
if (A[pos] < A[pos + 1]) break;
}
if (pos == -1) return false;
//posより大きい最小の数を二分探索
int ok = pos + 1;
int ng = len;
while (Math.abs(ng - ok) > 1) {
int mid = (ok + ng) / 2;
if (A[mid] > A[pos]) ok = mid;
else ng = mid;
}
swap(A, pos, ok);
reverse(A, pos + 1, len - 1);
return true;
}
//次の順列に書き換える、最小値ならfalseを返す
public static boolean prevPermutation(int A[]) {
int len = A.length;
int pos = len - 2;
for (; pos >= 0; pos--) {
if (A[pos] > A[pos + 1]) break;
}
if (pos == -1) return false;
//posより小さい最大の数を二分探索
int ok = pos + 1;
int ng = len;
while (Math.abs(ng - ok) > 1) {
int mid = (ok + ng) / 2;
if (A[mid] < A[pos]) ok = mid;
else ng = mid;
}
swap(A, pos, ok);
reverse(A, pos + 1, len - 1);
return true;
}
static <T> void swap(T[] x, int i, int j) {
T t = x[i];
x[i] = x[j];
x[j] = t;
}
static void swap(char[] x, int i, int j) {
char t = x[i];
x[i] = x[j];
x[j] = t;
}
static void swap(int[] x, int i, int j) {
int t = x[i];
x[i] = x[j];
x[j] = t;
}
public static String reverse(String a) {
StringBuilder sb = new StringBuilder();
sb.append(a);
return sb.reverse().toString();
}
public static void reverse(int[] x) {
int l = 0;
int r = x.length - 1;
while (l < r) {
int temp = x[l];
x[l] = x[r];
x[r] = temp;
l++;
r--;
}
}
public static void reverse(long[] x) {
int l = 0;
int r = x.length - 1;
while (l < r) {
long temp = x[l];
x[l] = x[r];
x[r] = temp;
l++;
r--;
}
}
public static void reverse(char[] x) {
int l = 0;
int r = x.length - 1;
while (l < r) {
char temp = x[l];
x[l] = x[r];
x[r] = temp;
l++;
r--;
}
}
public static void reverse(int[] x, int s, int e) {
int l = s;
int r = e;
while (l < r) {
int temp = x[l];
x[l] = x[r];
x[r] = temp;
l++;
r--;
}
}
static int cou(boolean[] a) {
int res = 0;
for (boolean b : a) {
if (b) res++;
}
return res;
}
static int cou(boolean[][] a) {
int res = 0;
for (boolean[] b : a) {
res += cou(b);
}
return res;
}
static int cou(String s, char c) {
int res = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == c) res++;
}
return res;
}
static int cou(char[][] a, char c) {
int co = 0;
for (int i = 0; i < a.length; i++)
for (int j = 0; j < a[0].length; j++)
if (a[i][j] == c) co++;
return co;
}
static int cou(int[] a, int key) {
int co = 0;
for (int i = 0; i < a.length; i++)
if (a[i] == key) co++;
return co;
}
static int cou(long[] a, long key) {
int co = 0;
for (int i = 0; i < a.length; i++)
if (a[i] == key) co++;
return co;
}
static int cou(int[][] a, int key) {
int co = 0;
for (int i = 0; i < a.length; i++)
co += (cou(a[i], key));
return co;
}
static int[] couArray(int[] a) {
int[] res = new int[maxs(a) + 1];
for (int i : a) {
res[i]++;
}
return res;
}
static void fill(int[] a, int v) {
Arrays.fill(a, v);
}
static void fill(long[] a, long v) {
Arrays.fill(a, v);
}
static void fill(boolean[] a, boolean v) {
Arrays.fill(a, v);
}
static void fill(int[][] a, int v) {
for (int i = 0; i < a.length; i++)
Arrays.fill(a[i], v);
}
static void fill(char[][] a, char c) {
for (int i = 0; i < a.length; i++)
Arrays.fill(a[i], c);
}
static void fill(long[][] a, long v) {
for (int i = 0; i < a.length; i++)
Arrays.fill(a[i], v);
}
static void fill(double[][] a, double v) {
for (int i = 0; i < a.length; i++)
Arrays.fill(a[i], v);
}
static void fill(boolean[][] a, boolean v) {
for (int i = 0; i < a.length; i++)
Arrays.fill(a[i], v);
}
static void fill(int[][][] a, int v) {
for (int i = 0; i < a.length; i++)
fill(a[i], v);
}
static void fill(long[][][] a, long v) {
for (int i = 0; i < a.length; i++)
fill(a[i], v);
}
static int maxs(int... a) {
int res = Integer.MIN_VALUE;
for (int i : a) {
res = Math.max(res, i);
}
return res;
}
static long maxs(long... a) {
long res = Long.MIN_VALUE;
for (long i : a) {
res = Math.max(res, i);
}
return res;
}
static double maxs(double... a) {
double res = Double.MIN_VALUE;
for (double i : a) {
res = Math.max(res, i);
}
return res;
}
static long mins(long... a) {
long res = Long.MAX_VALUE;
for (long i : a) {
res = Math.min(res, i);
}
return res;
}
static int maxs(int[][] ar) {
int res = Integer.MIN_VALUE;
for (int i[] : ar)
res = Math.max(res, maxs(i));
return res;
}
static long maxs(long[][] ar) {
long res = Integer.MIN_VALUE;
for (long i[] : ar)
res = Math.max(res, maxs(i));
return res;
}
static int mins(int... a) {
int res = Integer.MAX_VALUE;
for (int i : a) {
res = Math.min(res, i);
}
return res;
}
static int mins(int[][] ar) {
int res = Integer.MAX_VALUE;
for (int i[] : ar)
res = Math.min(res, mins(i));
return res;
}
public static <T extends Number> long sum(ArrayList<T> lis) {
long res = 0;
for (T li : lis) {
res += li.longValue();
}
return res;
}
static long sum(int[] a) {
long cou = 0;
for (int i : a)
cou += i;
return cou;
}
static long sum(long[] a) {
long cou = 0;
for (long i : a)
cou += i;
return cou;
}
//FastScanner
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tokenizer = null;
public static String next() {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public static String nextLine() {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
return reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken("\n");
}
public static long nl() {
return Long.parseLong(next());
}
public static String n() {
return next();
}
public static int ni() {
return Integer.parseInt(next());
}
public static double nd() {
return Double.parseDouble(next());
}
public static int[] nia(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = ni();
}
return a;
}
//1-index
public static int[] niao(int n) {
int[] a = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
a[i] = ni();
}
return a;
}
//番兵法
public static int[] nias(int n, int end) {
int[] a = new int[n + 1];
for (int i = 0; i < n; i++) {
a[i] = ni();
}
a[n] = end;
return a;
}
public static int[] niad(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = ni() - 1;
}
return a;
}
public static P[] npa(int n) {
P[] p = new P[n];
for (int i = 0; i < n; i++) {
p[i] = new P(ni(), ni());
}
return p;
}
public static P[] npad(int n) {
P[] p = new P[n];
for (int i = 0; i < n; i++) {
p[i] = new P(ni() - 1, ni() - 1);
}
return p;
}
public static int[][] nit(int h, int w) {
int[][] a = new int[h][w];
for (int hi = 0; hi < h; hi++) {
for (int wi = 0; wi < w; wi++) {
a[hi][wi] = ni();
}
}
return a;
}
public static int[][] nitd(int h, int w) {
int[][] a = new int[h][w];
for (int hi = 0; hi < h; hi++) {
for (int wi = 0; wi < w; wi++) {
a[hi][wi] = ni() - 1;
}
}
return a;
}
static int[][] S_ARRAY;
static long[][] S_LARRAY;
static int S_INDEX;
static int S_LINDEX;
//複数の配列を受け取る
public static int[] niah(int n, int k) throws Exception {
if (S_ARRAY == null) {
S_ARRAY = new int[k][n];
for (int j = 0; j < n; j++) {
for (int i = 0; i < k; i++) {
S_ARRAY[i][j] = ni();
}
}
}
return S_ARRAY[S_INDEX++];
}
public static long[] nlah(int n, int k) throws Exception {
if (S_LARRAY == null) {
S_LARRAY = new long[k][n];
for (int j = 0; j < n; j++) {
for (int i = 0; i < k; i++) {
S_LARRAY[i][j] = nl();
}
}
}
return S_LARRAY[S_LINDEX++];
}
//複数の配列を受け取る
public static int[] niahd(int n, int k) throws Exception {
if (S_ARRAY == null) {
S_ARRAY = new int[k][n];
for (int j = 0; j < n; j++) {
for (int i = 0; i < k; i++) {
S_ARRAY[i][j] = ni() - 1;
}
}
}
return S_ARRAY[S_INDEX++];
}
public static long[] nlahd(int n, int k) throws Exception {
if (S_LARRAY == null) {
S_LARRAY = new long[k][n];
for (int j = 0; j < n; j++) {
for (int i = 0; i < k; i++) {
S_LARRAY[i][j] = nl() - 1;
}
}
}
return S_LARRAY[S_LINDEX++];
}
public static char[] nca() {
char[] a = next().toCharArray();
return a;
}
public static String[] nsa(int n) {
String[] res = new String[n];
for (int i = 0; i < n; i++) {
res[i] = n();
}
return res;
}
//スペースが入っている場合
public static char[][] ncts(int h, int w) {
char[][] a = new char[h][w];
for (int hi = 0; hi < h; hi++) {
String s = nextLine().replace(" ", "");
for (int wi = 0; wi < s.length(); wi++) {
a[hi][wi] = s.charAt(wi);
}
}
return a;
}
public static char[][] nct(int h, int w) {
char[][] a = new char[h][w];
for (int hi = 0; hi < h; hi++) {
String s = nextLine();
for (int wi = 0; wi < s.length(); wi++) {
a[hi][wi] = s.charAt(wi);
}
}
return a;
}
public static char[][] nctp(int h, int w, char c) {
char[][] a = new char[h + 2][w + 2];
for (int hi = 1; hi < h + 1; hi++) {
String s = nextLine();
for (int wi = 1; wi < s.length() + 1; wi++) {
a[hi][wi] = s.charAt(wi - 1);
}
}
for (int wi = 0; wi < w + 2; wi++)
a[0][wi] = a[h + 1][wi] = c;
for (int hi = 0; hi < h + 2; hi++)
a[hi][0] = a[hi][w + 1] = c;
return a;
}
//スペースが入ってる時用
public static char[][] nctsp(int h, int w, char c) {
char[][] a = new char[h + 2][w + 2];
//char c = '*';
int i;
for (i = 0; i < w + 2; i++)
a[0][i] = c;
for (i = 1; i < h + 1; i++) {
a[i] = (c + nextLine().replace(" ", "") + c).toCharArray();
}
for (i = 0; i < w + 2; i++)
a[h + 1][i] = c;
return a;
}
public static long[] nla(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = nl();
}
return a;
}
public static long[] nlas(int n, long e) {
long[] a = new long[n + 1];
for (int i = 0; i < n; i++) {
a[i] = nl();
}
a[n] = e;
return a;
}
public static long[] nlao(int n) {
long[] a = new long[n + 1];
for (int i = 0; i < n; i++) {
a[i + 1] = nl();
}
return a;
}
public static long[] nlad(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = nl() - 1;
}
return a;
}
public static long[][] nlt(int h, int w) {
long[][] a = new long[h][w];
for (int hi = 0; hi < h; hi++) {
for (int wi = 0; wi < w; wi++) {
a[hi][wi] = nl();
}
}
return a;
}
//便利クラス
static class CouMap {
public HashMap<Long, Long> map;
public HashMap<String, Long> smap;
CouMap() {
map = new HashMap();
smap = new HashMap();
}
CouMap(int[] a) {
map = new HashMap();
smap = new HashMap();
for (int i : a) {
put(i);
}
}
public int size() {
return map.size();
}
public void put(long key, long value) {
Long nowValue = map.get(key);
map.put(key, nowValue == null ? value : nowValue + value);
}
public void put(String key, long value) {
Long nowValue = smap.get(key);
smap.put(key, nowValue == null ? value : nowValue + value);
}
public void mput(long key, long value) {
Long nowValue = map.get(key);
map.put(key, nowValue == null ? value % MOD : mSum(nowValue, value));
}
public void put(long key) {
put(key, 1);
}
public void put(String key) {
put(key, 1);
}
public void put(int... arg) {
for (int i : arg) {
put(i, 1);
}
}
public void put(long... arg) {
for (long i : arg) {
put(i, 1);
}
}
public void mput(int... arg) {
for (int i : arg) {
mput(i, 1);
}
}
public void mput(long... arg) {
for (long i : arg) {
mput(i, 1);
}
}
public long get(long key) {
Long v = map.get(key);
return v == null ? 0 : v;
}
public long get(String key) {
Long v = map.get(key);
return v == null ? 0 : v;
}
}
static class P implements Comparable<P> {
int x, y;
@Override
public int compareTo(P p) {
//xyで昇順
return x == p.x ? y - p.y : x - p.x;
//xyで降順
//return (nowx == p.nowx ? nowy - p.nowy : nowx - p.nowx) * -1;
//yxで昇順
//return nowy == p.nowy ? nowx - p.nowx : nowy - p.nowy;
//yxで昇順
//return (nowy == p.nowy ? nowx - p.nowx : nowy - p.nowy) * -1;
//x昇 y降
//return nowx == p.nowx ? p.nowy - nowy : nowx - p.nowx;
//x降 y昇
//return (nowx == p.nowx ? p.nowy - nowy : nowx - p.nowx) * -1;
//y昇 x降
//return nowy == p.nowy ? p.nowx - nowx : nowy - p.nowy;
//y降 x昇
//return (nowy == p.nowy ? p.nowx - nowx : nowy - p.nowy) * -1;
}
P(int a, int b) {
x = a;
y = b;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof P)) return false;
P p = (P) o;
return x == p.x && y == p.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}
static class PL implements Comparable<PL> {
long x, y;
public int compareTo(PL p) {
//xyで昇順
long res = x == p.x ? y - p.y : x - p.x;
//xyで降順
//long res = (nowx == p.nowx ? nowy - p.nowy : nowx - p.nowx) * -1;
//yxで昇順
//long res = nowy == p.nowy ? nowx - p.nowx : nowy - p.nowy;
//yxで昇順
//long res = (nowy == p.nowy ? nowx - p.nowx : nowy - p.nowy) * -1;
//x昇 y降
//long res = nowx == p.nowx ? p.nowy - nowy : nowx - p.nowx;
//x降 y昇
//long res = (nowx == p.nowx ? p.nowy - nowy : nowx - p.nowx) * -1;
//y昇 x降
//long res = nowy == p.nowy ? p.nowx - nowx : nowy - p.nowy;
//y降 x昇
//long res = (nowy == p.nowy ? p.nowx - nowx : nowy - p.nowy) * -1;
return (res == 0) ? 0 : res > 0 ? 1 : -1;
}
PL(long a, long b) {
x = a;
y = b;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof PL)) return false;
PL p = (PL) o;
return x == p.x && y == p.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}
//値を渡す際は半開区間
static class RectangleSum {
//半開区間 0は0
long[][] rui;
int H, W;
RectangleSum(long[][] ori) {
H = ori.length;
W = ori[0].length;
rui = new long[H + 1][W + 1];
for (int hi = 0; hi < H; hi++) {
for (int wi = 0; wi < W; wi++) {
rui[hi + 1][wi + 1] = ori[hi][wi];
}
}
for (int hi = 1; hi < H + 1; hi++) {
for (int wi = 1; wi < W + 1; wi++) {
rui[hi][wi] += rui[hi - 1][wi];
rui[hi][wi] += rui[hi][wi - 1];
rui[hi][wi] -= rui[hi - 1][wi - 1];
}
}
}
RectangleSum(int[][] ori) {
H = ori.length;
W = ori[0].length;
rui = new long[H + 1][W + 1];
for (int hi = 0; hi < H; hi++) {
for (int wi = 0; wi < W; wi++) {
rui[hi + 1][wi + 1] = ori[hi][wi];
}
}
for (int hi = 1; hi < H + 1; hi++) {
for (int wi = 1; wi < W + 1; wi++) {
rui[hi][wi] += rui[hi - 1][wi];
rui[hi][wi] += rui[hi][wi - 1];
rui[hi][wi] -= rui[hi - 1][wi - 1];
}
}
}
//半開区間
public long getSum(int left, int right, int top, int bottom) {
if (right > W || bottom > H) return 0;
if (left < 0 || top < 0) return 0;
if (top >= bottom || left >= right) return 0;
long res = rui[bottom][right];
res -= rui[top][right];
res -= rui[bottom][left];
res += rui[top][left];
return res;
}
}
public static void main(String[] args) throws Exception {
long startTime = System.currentTimeMillis();
solve();
System.out.flush();
long endTime = System.currentTimeMillis();
if (DEBUG) System.err.println(endTime - startTime);
}
}