結果

問題 No.1505 Zero-Product Ranges
ユーザー CaliPotaCaliPota
提出日時 2021-05-14 22:32:51
言語 Java21
(openjdk 21)
結果
AC  
実行時間 114 ms / 2,000 ms
コード長 24,367 bytes
コンパイル時間 3,109 ms
コンパイル使用メモリ 92,716 KB
実行使用メモリ 52,356 KB
最終ジャッジ日時 2024-04-10 01:07:32
合計ジャッジ時間 9,193 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 54 ms
50,404 KB
testcase_01 AC 53 ms
50,392 KB
testcase_02 AC 52 ms
50,288 KB
testcase_03 AC 101 ms
51,824 KB
testcase_04 AC 104 ms
52,328 KB
testcase_05 AC 87 ms
51,780 KB
testcase_06 AC 87 ms
51,840 KB
testcase_07 AC 84 ms
51,304 KB
testcase_08 AC 85 ms
51,308 KB
testcase_09 AC 86 ms
51,776 KB
testcase_10 AC 86 ms
51,452 KB
testcase_11 AC 87 ms
51,680 KB
testcase_12 AC 83 ms
51,412 KB
testcase_13 AC 85 ms
51,900 KB
testcase_14 AC 90 ms
51,828 KB
testcase_15 AC 90 ms
51,952 KB
testcase_16 AC 111 ms
52,356 KB
testcase_17 AC 111 ms
52,200 KB
testcase_18 AC 102 ms
52,196 KB
testcase_19 AC 53 ms
50,376 KB
testcase_20 AC 54 ms
50,292 KB
testcase_21 AC 54 ms
50,352 KB
testcase_22 AC 109 ms
52,156 KB
testcase_23 AC 111 ms
52,164 KB
testcase_24 AC 109 ms
52,296 KB
testcase_25 AC 108 ms
52,208 KB
testcase_26 AC 107 ms
52,048 KB
testcase_27 AC 110 ms
52,280 KB
testcase_28 AC 108 ms
52,156 KB
testcase_29 AC 110 ms
52,076 KB
testcase_30 AC 109 ms
52,304 KB
testcase_31 AC 114 ms
52,288 KB
testcase_32 AC 84 ms
52,076 KB
testcase_33 AC 85 ms
52,052 KB
testcase_34 AC 97 ms
52,128 KB
testcase_35 AC 93 ms
52,096 KB
testcase_36 AC 85 ms
52,072 KB
testcase_37 AC 85 ms
51,824 KB
testcase_38 AC 83 ms
51,968 KB
testcase_39 AC 87 ms
51,828 KB
testcase_40 AC 85 ms
51,708 KB
testcase_41 AC 88 ms
52,060 KB
testcase_42 AC 66 ms
50,724 KB
testcase_43 AC 79 ms
50,760 KB
testcase_44 AC 65 ms
50,324 KB
testcase_45 AC 67 ms
50,624 KB
testcase_46 AC 59 ms
49,912 KB
testcase_47 AC 69 ms
51,072 KB
testcase_48 AC 63 ms
50,492 KB
testcase_49 AC 56 ms
50,516 KB
testcase_50 AC 62 ms
50,428 KB
testcase_51 AC 69 ms
50,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.NoSuchElementException;

	//@Japanese
	/* PriorityQueueは拡張for文で出すとsortされてない順番で出てくる
	 * longのbit演算は1L<<posに注意
	 * JOIはMLEが厳しい。最悪shortを使う。
	 * ArrayListはオートボクシングが遅いから、最悪自作listを使う
	 */

	/*略語
	 * 2-to, 4-for, 8-from
	 * -L -long(型), -P -素数Pを法とした余り
	 * a,b -任意の引数, n,m -自然数, p -素数
	 * pos -postition
	 * abs -絶対値
	 * min -minimum, max -maximum, ave -average
	 * div -divide
	 * pow -power(累乗)
	 * ceil -ceiling(天井関数)
	 * dt -data
	 * ln -length
	 * sc -scanner
	 * INF -INFINITY
	 * e97 -10E9+7=1000000007(prime often used)
	 */

	// How about n=1, h*w=1*x

	public class Main {
		public static void main(String[] args) throws Exception {

			FastScanner sc = new FastScanner();
			PrintWriter out = new PrintWriter(System.out);

			
			
			int n = sc.nexI();
			
			long suc =0;
			ArrayList<Long> ecp = new ArrayList<>();
			for(int i=0; i<n; i++) {
				int fl = sc.nexI();
				if(fl==0) {
					if(suc>0) {
						ecp.add(suc);
						suc=0;
					}
				}else {
					suc++;
				}
			}
			if(suc>0) {
				ecp.add(suc);
			}
			
			long ans = nC2((long)n+1);
			for(long e: ecp) ans -= nC2(e+1);
			System.out.println(ans);

			out.flush();
			return;
		}
		
		

	    private static long[] facP = null;
	    private static long[] finvP = null;
	    private static int[] legendre_order = null;
	    private static long prime4nCk = 0;
	    
	    private static void Cinit(int max_sz, long p, boolean is_p_large_enough){
	    	prime4nCk=p;
	        facP = new long[max_sz+1];
	        finvP = new long[max_sz+1];
			legendre_order = new int[max_sz + 1];
			facP[0] = 1L;
			finvP[0] = 1L;

			long[] rem = new long[max_sz + 1];
			for (int i = 1; i <= max_sz; i++) {
				rem[i] = (long)i;
				legendre_order[i] = legendre_order[i - 1];
				while (rem[i] % prime4nCk == 0) {
					rem[i] /= prime4nCk;
					legendre_order[i]++;
				}
				rem[i] %= prime4nCk;
				facP[i] = (facP[i - 1] * rem[i]) % prime4nCk;
				finvP[i] = (int) modinv(facP[i], prime4nCk);
			}
	        
	        finvP[max_sz] = modinv(facP[max_sz], prime4nCk);
			for(int i=max_sz; i>1; i--){
			    finvP[i-1] = (finvP[i]*rem[i]) % prime4nCk;
			}
	    }

	    private static long C10e97(int n, int k){
			int ex = legendre_order[n];
			ex -= legendre_order[k];
			ex -= legendre_order[n - k];
			if (ex > 0) return 0;
	        long ans = facP[n];
	        ans *= finvP[k];
	        ans %= prime4nCk;
	        ans *= finvP[n-k];
	        ans %= prime4nCk;
	        if(ans<0) return ans+prime4nCk;
	        else return ans;
	    }
		private static long P10e97(int n, int k){
	        long ans = facP[n];
	        ans *= finvP[n-k];
	        ans %= prime4nCk;
	        if(ans<0) return ans+prime4nCk;
	        else return ans;
		}
	    private static long C10e97LS(long n, int k){
	        long ans =1;
	        for(long i=n; i>(n-k); i--){
	            ans *= i;
	            ans %= prime4nCk;
	        }
	        ans *= modinv(facP[k],prime4nCk);
	        return ans%prime4nCk;
	    }



		private static final int INF = (int) 3e8;
		private static final long INFL = (long) 1e17;
		private static final int INTMAX = Integer.MAX_VALUE;
		private static final long LONGMAX = Long.MAX_VALUE;
		private static final long e97 = 1000000007L;
		private static final long e99 = 998244353L;
		private static final double PI = Math.PI;

		private static void assertion(boolean should_true) {
			// throw Error if should_true is not true @Japanese「断言」
			if (!should_true)
				throw new AssertionError();
		}

		private static int abs(int a) {
			return (a >= 0) ? a : -a;
		}

		private static long abs(long a) {
			return (a >= 0L) ? a : -a;
		}

		private static double abs(double a) {
			return (a >= 0.0) ? a : -a;
		}

		private static int min(int a, int b) {
			return (a < b) ? a : b;
		}

		private static long min(long a, long b) {
			return (a < b) ? a : b;
		}

		private static double min(double a, double b) {
			return (a < b) ? a : b;
		}

		private static int max(int a, int b) {
			return (a > b) ? a : b;
		}

		private static long max(long a, long b) {
			return (a > b) ? a : b;
		}

		private static double max(double a, double b) {
			return (a > b) ? a : b;
		}

		private static int pow2(int num2pow) {
			if (num2pow > 4e4)
				throw new IllegalArgumentException("Input is to Large. Use Long.");
			return num2pow * num2pow;
		}

		private static long pow2(long num2pow) {
			if (num2pow > 1e8)
				throw new IllegalArgumentException("Input is to Large. Use PowP.");
			return num2pow * num2pow;
		}

		private static int pow(int num_powered, int index) {
			int ans = 1;
			for (int i = 0; i < index; i++) {
				if (ans >= (INTMAX / num_powered))
					throw new IllegalArgumentException("Input is to Large. Use Long.");
				ans *= num_powered;
			}
			return ans;
		}

		private static long pow(long num_powered, int index) {
			long ans = 1L;
			for (int i = 0; i < index; i++) {
				if (ans >= (LONGMAX / num_powered))
					throw new IllegalArgumentException("Input is to Large. Use PowP.");
				ans *= num_powered;
			}
			return ans;
		}

		private static long powP(long num_powered, long index, long p) {
			// O(log(index))
			// @Japanese 繰り返し二乗法
			if (num_powered == 0L)
				return 0L;
			if (index == 0L)
				return 1L;
			if (index == 2L) {
				return (pow2(num_powered) % p);
			}

			int d = getDigit2(index);
			long[] num_done_by2 = new long[d + 1];
			num_done_by2[0] = num_powered;
			for (int i = 1; i <= d; i++) {
				num_done_by2[i] = num_done_by2[i - 1] * num_done_by2[i - 1];
				num_done_by2[i] %= p;
			}
			long ans = 1L;
			for (int i = d; i >= 0; i--) {
				long cf = (1L << (long) i);
				if (index >= cf) {
					index -= cf;
					ans = ans * num_done_by2[i];
					ans %= p;
				}
			}
			return ans;
		}

		private static double hypod(double a, double b) {
			return Math.sqrt(a * a + b * b);
		}

		private static int getDigit2(long num2know) {
			// O(log(n))
			long compare4 = 1L;
			int digit = 0;
			while (num2know >= compare4) {
				digit++;
				compare4 = (1L << (long) digit);
			}
			return digit;
			// num < 2^digit
		}

		private static int getDigit10(long num2know) {
			// O(log10(n))
			if(num2know<0L) throw new IllegalArgumentException("Input is Negative");
			if(num2know>=1000000000000000000L) return 19;
			long compare4 = 1L;
			int digit = 0;
			while (num2know >= compare4) {
				digit++;
				compare4 *= 10L;
			}
			return digit; // @Japanese num は digit桁の数で、10^digit未満

		}

		private static int divceil(int numerator, int denominator) {
			return (numerator + denominator - 1) / denominator;
		}

		private static long divceil(long numerator, long denominator) {
			return (numerator + denominator - 1L) / denominator;
		}

		private static long factorial(int n) {
			// O(n)
			long ans = 1L;
			for (long i = 2; i <= n; i++) {
				if (ans >= (LONGMAX / i))
					throw new IllegalArgumentException("Input is to Large. Use facP.");
				ans *= i;
			}
			return ans;
		}

		private static long facP(int n, long p) {
			// O(n) see also PermulationCombination:O(max_sz)+Q
			long ans = 1L;
			for (long i = 2; i <= n; i++) {
				ans *= i;
				ans %= p;
			}
			return ans;
		}

		private static long lcm(long m, long n) {
			long ans = m / gcd(m, n);
			if (ans >= (LONGMAX / n))
				throw new IllegalArgumentException("Input is to Large.");
			ans *= n;
			return ans;
		}

		private static long gcd(long m, long n) {
			// O(log(m+n))
			if ((m <= 0L) || (n <= 0L))
				throw new IllegalArgumentException("m and n should be natural.");

			while ((m > 0L) && (n > 0L)) {
				if (m >= n)
					m %= n;
				else
					n %= m;
			}
			if (m > 0L)
				return m;
			else
				return n;
		}

		private static boolean is_prime(long n2check) {
			// @Japanese O(√n)
			if (n2check == 1L)
				return false;
			for (long i = 2L; i <= Math.sqrt(n2check); i++) {
				if (n2check % i == 0L)
					return false;
			}
			return true;
		}
		private static int isSquare(long n) {
			double sq = Math.sqrt(n);
			long ans = (long)sq;
			if((ans *ans) == n) return (int)ans;
			else return -1;
		}



		private static int safe_mod(int n, int p) {
			n %= p;
			if (n >= 0)
				return n;
			return (n + p);
		}

		private static long safe_mod(long n, long p) {
			n %= p;
			if (n >= 0L)
				return n;
			return (n + p);
		}

		private static long modinv(long n, long p) {
			// @Japanese 逆元を求める
			// O(10log(n))
			// pは素数でなくてもよい
			// ネットから拾ってきたのが理解不能だったので、行列計算を用いて非効率的アルゴリズムを書いた

			n %= p;
			if ((p == 1L) || (gcd(n, p) != 1L))
				throw new IllegalArgumentException("n and p should be coprime.");

			// @Japanese
			// yn≡1(mod p)
			// <-> xp+yn=1; (n<p)
			// ...(sx+ty)a+(ux+vy)b=1 (|sv-tu|=1)
			// ...(sx+ty)a+(ux+vy)=1
			// <- sx+ty=0, ux+vy=1

			long a = p, b = n, s = 1L, t = 0L, u = 0L, v = 1L;
			while (b > 1) {
				long quo = a / b, rem = a % b;
				a = b;
				b = rem;
				long s2 = s * quo + u, t2 = t * quo + v;
				u = s;
				v = t;
				s = s2;
				t = t2;
			}
			long det = s * v - t * u;
			if (abs(det) != 1L)
				throw new ArithmeticException("My algorithm was Wrong!!");
			s /= det;
			s %= p;
			if (s < 0L)
				s += p;
			return s;
		}

		private static int minAll(int[] dt4min) {
			// O(n)
			int min = INF;
			for (int element : dt4min) {
				if (element < min)
					min = element;
			}
			return min;
		}

		private static long minAll(long[] dt4min) {
			// O(n)
			long min = INFL;
			for (long element : dt4min) {
				if (element < min)
					min = element;
			}
			return min;
		}

		private static int maxAll(int[] dt4max) {
			// O(n)
			int max = -INF;
			for (int element : dt4max) {
				if (element > max)
					max = element;
			}
			return max;
		}

		private static long maxAll(long[] dt4max) {
			// O(n)
			long max = -INFL;
			for (long element : dt4max) {
				if (element > max)
					max = element;
			}
			return max;
		}

		private static int sumAll(int[] dt4sum) {
			// O(n)
			int sum_of_dt = 0;
			for (int element : dt4sum) {
				if (sum_of_dt > (INTMAX - element))
					throw new IllegalArgumentException("Input is to Large. Use Long.");
				sum_of_dt += element;
			}
			return sum_of_dt;
		}

		private static long sumAll(long[] dt4sum) {
			// O(n)
			long sum_of_dt = 0L;
			for (long element : dt4sum) {
				if (sum_of_dt > (LONGMAX - element))
					throw new IllegalArgumentException("Input is to Large.");
				sum_of_dt += element;
			}
			return sum_of_dt;
		}

		private static int sumAll(ArrayList<Integer> dt4sum) {
			int sum_of_dt = 0;
			for (long element : dt4sum) {
				if (sum_of_dt > (INTMAX - element))
					throw new IllegalArgumentException("Input is to Large. Use Long.");
				sum_of_dt += element;
			}
			return sum_of_dt;
		}

		private static int[] reverse(int[] as) {
			int ln = as.length;
			int[] bs = new int[ln];
			for (int i = 0; i < ln; i++)
				bs[i] = as[ln - i - 1];
			return bs;
		}

		private static void reverseSub(int[] as, int S_include, int Gnot_include) {
			// O(G-S)
			int ln = Gnot_include - S_include;

			int[] bs = new int[ln];
			for (int i = S_include; i < Gnot_include; i++)
				bs[i - S_include] = as[i];
			for (int i = 0; i < ln; i++)
				as[i + S_include] = bs[ln - i - 1];
		}

		private static boolean is_in_area(int y, int x, int height, int width) {
			if (y < 0)
				return false;
			if (x < 0)
				return false;
			if (y >= height)
				return false;
			if (x >= width)
				return false;
			return true;
		}

		private static boolean is_in_area(Vector v, int height, int width) {
			if (v.y < 0)
				return false;
			if (v.x < 0)
				return false;
			if (v.y >= height)
				return false;
			if (v.x >= width)
				return false;
			return true;
		}

		private static int nC2(int n) {
			return ((n * (n - 1)) / 2);
		}

		private static long nC2(long n) {
			return ((n * (n - 1L)) / 2L);
		}

		private static int iflag(int pos) {
			if (pos >= 32)
				throw new IllegalArgumentException("Input is to Large. Use Long.");
			return (1 << pos);
		}

		private static long flag(int pos) {
			if (pos >= 64)
				throw new IllegalArgumentException("Input is to Large. Use Long.");
			return (1L << (long) pos);
		}

		private static boolean isFlaged(int bit, int pos) {
			if (pos >= 32)
				throw new IllegalArgumentException("Input is to Large.");
			return ((bit & (1 << pos)) != 0);
		}

		private static boolean isFlaged(long bit, int pos) {
			if (pos >= 64)
				throw new IllegalArgumentException("Input is to Large.");
			return ((bit & (1L << (long) pos)) != 0L);
		}

		private static int deflag(int bit, int pos) {
			return (bit & (~(1 << pos)));
		}

		private static int countFlaged(int bit) {
			int ans = 0;
			for (int i = 0; i < 31; i++) {
				if ((bit & (1 << i)) != 0)
					ans++;
			}
			return ans;
		}

		private static int countFlaged(long bit) {
			int ans = 0;
			for (long i = 0L; i < 63L; i++) {
				if ((bit & (1L << i)) != 0L)
					ans++;
			}
			return ans;
		}

		private static int[] Xdir4 = { 1, 0, 0, -1 };
		private static int[] Ydir4 = { 0, 1, -1, 0 };
		private static int[] Xdir8 = { 1, 1, 1, 0, 0, -1, -1, -1 };
		private static int[] Ydir8 = { 1, 0, -1, 1, -1, 1, 0, -1 };

		public static int biSearch(int[] dt, int target) {
			// O(log(dt.length))
			// dt should be sorted in 0->INF
			// return adress of target
			int left = 0, right = dt.length - 1;
			int mid = -1;
			while (left <= right) {
				mid = ((right + left) / 2);
				if (dt[mid] == target)
					return mid;
				if (dt[mid] < target)
					left = (mid + 1);
				else
					right = (mid - 1);
			}
			return -1;
		}

		public static int biSearchMax(long[] dt, long target) {
			// O(log(dt.length))
			// dt should be sorted in 0->INF
			int left = -1, right = dt.length, mid = -1;
			while ((right - left) > 1) {
				mid = ((right + left) / 2);
				if (dt[mid] <= target)
					left = mid;
				else
					right = mid;
			}
			return left;
			// @Japanese target以下の最大のaddress
		}

		public static int biSearchMin(long[] dt, long target) {
			// O(log(dt.length))
			// dt should be sorted in 0->INF
			int left = -1, right = dt.length, mid = -1;
			while ((right - left) > 1) {
				mid = ((right + left) / 2);
				if (dt[mid] <= target)
					left = mid;
				else
					right = mid;
			}
			return right;
			// @Japanese targetより大きい最小のaddress
		}

		private static void fill(boolean[] target, boolean reset) {
			for (int i = 0; i < target.length; i++)
				target[i] = reset;
		}

		private static void fill(int[] target, int reset) {
			for (int i = 0; i < target.length; i++)
				target[i] = reset;
		}

		private static void fill(long[] target, long reset) {
			for (int i = 0; i < target.length; i++)
				target[i] = reset;
		}

		private static void fill(char[] target, char reset) {
			for (int i = 0; i < target.length; i++)
				target[i] = reset;
		}

		private static void fill(double[] target, double reset) {
			for (int i = 0; i < target.length; i++)
				target[i] = reset;
		}

		private static void fill(boolean[][] target, boolean reset) {
			for (int i = 0; i < target.length; i++) {
				for (int j = 0; j < target[i].length; j++) {
					target[i][j] = reset;
				}
			}
		}

		private static void fill(int[][] target, int reset) {
			for (int i = 0; i < target.length; i++) {
				for (int j = 0; j < target[i].length; j++) {
					target[i][j] = reset;
				}
			}
		}

		private static void fill(long[][] target, long reset) {
			for (int i = 0; i < target.length; i++) {
				for (int j = 0; j < target[i].length; j++) {
					target[i][j] = reset;
				}
			}
		}

		private static void fill(char[][] target, char reset) {
			for (int i = 0; i < target.length; i++) {
				for (int j = 0; j < target[i].length; j++) {
					target[i][j] = reset;
				}
			}
		}

		private static void fill(double[][] target, double reset) {
			for (int i = 0; i < target.length; i++) {
				for (int j = 0; j < target[i].length; j++) {
					target[i][j] = reset;
				}
			}
		}

		private static void fill(int[][][] target, int reset) {
			for (int i = 0; i < target.length; i++) {
				for (int j = 0; j < target[i].length; j++) {
					for (int k = 0; k < target[i][j].length; k++) {
						target[i][j][k] = reset;
					}
				}
			}
		}

		private static void fill(long[][][] target, long reset) {
			for (int i = 0; i < target.length; i++) {
				for (int j = 0; j < target[i].length; j++) {
					for (int k = 0; k < target[i][j].length; k++) {
						target[i][j][k] = reset;
					}
				}
			}
		}
		private static void fill(double[][][] target, double reset) {
			for (int i = 0; i < target.length; i++) {
				for (int j = 0; j < target[i].length; j++) {
					for (int k = 0; k < target[i][j].length; k++) {
						target[i][j][k] = reset;
					}
				}
			}
		}

		private static void fill_parent(int[] parent) {
			for (int i = 0; i < parent.length; i++) {
				parent[i] = i;
			}
		}

		private static void showBit(int bit) {
			for (int i = 0; i < getDigit2(bit); i++) {
				if (isFlaged(bit, i))
					System.out.print("O");
				else
					System.out.print(".");
			}
			System.out.println();
		}

		private static void showBit(long bit) {
			for (int i = 0; i < getDigit2(bit); i++) {
				if (isFlaged(bit, i))
					System.out.print("O");
				else
					System.out.print(".");
			}
			System.out.println();
		}

		static void show2(boolean[][] dt, String cmnt) {
			for (int i = 0; i < dt.length; i++) {
				for (int j = 0; j < dt[i].length; j++) {
					if (dt[i][j])
						System.out.print("O");
					else
						System.out.print(".");
				}
				if (!cmnt.equals(""))
					System.out.print("<-" + cmnt);
				System.out.println(" :" + i);
			}
		}

		static void show2(int[][] dt, String cmnt) {
			for (int i = 0; i < dt.length; i++) {
				for (int j = 0; j < dt[i].length; j++)
					System.out.print(dt[i][j] + ",");
				if (!cmnt.equals(""))
					System.out.print("<-" + cmnt);
				System.out.println(" :" + i);
			}
		}

		static void show2(long[][] dt, String cmnt) {
			for (int i = 0; i < dt.length; i++) {
				for (int j = 0; j < dt[i].length; j++)
					System.out.print(dt[i][j] + ",");
				if (!cmnt.equals(""))
					System.out.print("<-" + cmnt);
				System.out.println(" :" + i);
			}
		}

		static void show2(ArrayDeque<Long> dt) {
			long element = 0;
			while (dt.size() > 0) {
				element = dt.removeFirst();
				System.out.print(element);
			}
			System.out.println("\n");
		}

		static void show2(List<Object> dt) {
			for (int i = 0; i < dt.size(); i++)
				System.out.print(dt.get(i) + ",");
			System.out.println("\n");
		}

		private static void prtlnas(int[] array, PrintWriter out) {
			for (int e: array)
				out.println(e);
			out.flush();
		}

		private static void prtlnas(long[] array, PrintWriter out) {
			for (long e: array)
				out.println(e);
			out.flush();
		}

		private static void prtlnas(ArrayList<Object> array, PrintWriter out) {
			for (Object e: array)
				out.println(e);
			out.flush();
		}

		private static void prtspas(int[] array, PrintWriter out) {
			out.print(array[0]);
			for (int i = 1; i < array.length; i++)
				out.print(" " + array[i]);
			out.println();
			out.flush();
		}

		private static void prtspas(long[] array, PrintWriter out) {
			out.print(array[0]);
			for (int i = 1; i < array.length; i++)
				out.print(" " + array[i]);
			out.println();
			out.flush();
		}

		private static void prtspas(double[] array, PrintWriter out) {
			out.print(array[0]);
			for (int i = 1; i < array.length; i++)
				out.print(" " + array[i]);
			out.println();
			out.flush();
		}

		private static void prtspas(List<Integer> array, PrintWriter out) {
			if (array.isEmpty())
				return;
			out.print(array.get(0));
			for (int i = 1; i < array.size(); i++)
				out.print(" " + array.get(i));
			out.println();
			out.flush();
		}

		static class Vector {
			int x, y;

			public Vector(int sx, int sy) {
				this.x = sx;
				this.y = sy;
			}

			public boolean equals(Vector v) {
				return (this.x == v.x && this.y == v.y);
			}

			public void show2() {
				System.out.println(this.x + ", " + this.y);
			}

			public static int dist2(Vector a, Vector b) {
				int dx = abs(a.x - b.x);
				int dy = abs(a.y - b.y);
				if (dx > 3e4)
					throw new IllegalArgumentException("Input is to Large. Use Long.");
				if (dy > 3e4)
					throw new IllegalArgumentException("Input is to Large. Use Long.");
				return (dx * dx + dy * dy);
			}
		}

		static class CompVector implements Comparator<Vector> {
			public int compare(Vector a, Vector b) {
				if (a.x == b.x)
					return a.y - b.y;
				else
					return a.x - b.x;
			}
		}

		static class FastScanner {
			//@Japanese ネットから拾ってきた。よく分からん。
			private final InputStream in = System.in;
			private final byte[] buffer = new byte[1024];
			private int ptr = 0;
			private int buflen = 0;

			private boolean hasNextByte() {
				if (ptr < buflen) {
					return true;
				} else {
					ptr = 0;
					try {
						buflen = in.read(buffer);
					} catch (IOException e) {
						e.printStackTrace();
					}
					if (buflen <= 0) {
						return false;
					}
				}
				return true;
			}

			private int readByte() {
				if (hasNextByte())
					return buffer[ptr++];
				else
					return -1;
			}

			private static boolean isPrintableChar(int c) {
				return (33 <= c) && (c <= 126);
			}

			public boolean hasNext() {
				while (hasNextByte() && !isPrintableChar(buffer[ptr]))
					ptr++;
				return hasNextByte();
			}

			public String next() {
				if (!hasNext())
					throw new NoSuchElementException();
				StringBuilder sb = new StringBuilder();
				int b = readByte();
				while (isPrintableChar(b)) {
					sb.appendCodePoint(b);
					b = readByte();
				}
				return sb.toString();
			}

			public long nexL() {
				if (!hasNext())
					throw new NoSuchElementException();
				long n = 0;
				boolean minus = false;
				int b = readByte();
				if (b == '-') {
					minus = true;
					b = readByte();
				}
				if (b < '0' || '9' < b) {
					throw new NumberFormatException();
				}
				while (true) {
					if ('0' <= b && b <= '9') {
						n *= 10;
						n += b - '0';
					} else if (b == -1 || !isPrintableChar(b) || b == ':') {
						return minus ? -n : n;
					} else {
						throw new NumberFormatException();
					}
					b = readByte();
				}
			}

			public int nexI() {
				long nl = nexL();
				if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
					throw new NumberFormatException();
				}
				return (int) nl;
			}

			public double nexD() {
				return Double.parseDouble(next());
			}

			public int[] ai(int ln) {
				int[] as = new int[ln];
				for (int i = 0; i < ln; i++) {
					as[i]=nexI();
				}
				return as;
			}

			public long[] al(int ln) {
				long[] as = new long[ln];
				for (int i = 0; i < ln; i++) {
					as[i]=nexL();
				}
				return as;
			}
			// a means array
			public void ai(int[]... array) {
				for (int i = 0; i < array[0].length; i++) {
					for (int j = 0; j < array.length; j++) {
						array[j][i] = nexI();
					}
				}
				return;
			}

			public void al(long[]... array) {
				for (int i = 0; i < array[0].length; i++) {
					for (int j = 0; j < array.length; j++) {
						array[j][i] = nexL();
					}
				}
				return;
			}

			public void aimin1(int[] array) {
				for (int i = 0; i < array.length; i++) {
					array[i] = nexI() - 1;
				}
				return;
			}

			public void aD(double[]... array) {
				for (int i = 0; i < array[0].length; i++) {
					for (int j = 0; j < array.length; j++) {
						array[j][i] = nexD();
					}
				}
				return;
			}

			public void ai2d(int[][] array) {
				for (int i = 0; i < array.length; i++) {
					for (int j = 0; j < array[0].length; j++) {
						array[i][j] = nexI();
					}
				}
				return;
			}

			public void al2d(long[][] array) {
				for (int i = 0; i < array.length; i++) {
					for (int j = 0; j < array[0].length; j++) {
						array[i][j] = nexL();
					}
				}
				return;
			}
		}
	}
	// END OF THE CODE
0