Advertisement
islomiddin

YandexAlgo2017:A

Apr 30th, 2017
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.15 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         InputStream inputStream = System.in;
  6.         OutputStream outputStream = System.out;
  7.         InputReader in = new InputReader(inputStream);
  8.         PrintWriter out = new PrintWriter(outputStream);
  9.         Solver solver = new Solver();
  10.         solver.solve(in, out);
  11.         out.close();
  12.     }
  13.     static class Solver {
  14.         public void solve(InputReader in, PrintWriter out) {
  15.             int n = in.nextInt();
  16.             int[] a = new int[n];
  17.             int[] index = new int[n + 1];
  18.             for (int i = 0; i < n; ++i) {
  19.                 a[i] = in.nextInt();
  20.                 index[a[i]] = i;
  21.             }
  22.             if (n == 1) {
  23.                 out.println(1);
  24.                 return;
  25.             }
  26.             int ind = index[1], moves = 0;
  27.             while (true) {
  28.                 if (index[a[ind] + 1] < ind) {
  29.                     ++moves;
  30.                 }
  31.                 ind = index[a[ind] + 1];
  32.                 if (a[ind] == n) {
  33.                     out.println(moves + 1);
  34.                     return;
  35.                 }
  36.             }
  37.         }
  38.     } // wubba lubba dub dub
  39.     static class InputReader {
  40.         public BufferedReader reader;
  41.         public StringTokenizer tokenizer;
  42.         public InputReader(InputStream stream) {
  43.             reader = new BufferedReader(new InputStreamReader(stream), 32768);
  44.             tokenizer = null;
  45.         }
  46.         public String next() {
  47.             while (tokenizer == null || !tokenizer.hasMoreElements()) {
  48.                 try {
  49.                     tokenizer = new StringTokenizer(reader.readLine());
  50.                 } catch (IOException e) {
  51.                     throw new RuntimeException(e);
  52.                 }
  53.             }
  54.             return tokenizer.nextToken();
  55.         }
  56.         public int nextInt() {
  57.             return Integer.parseInt(next());
  58.         }
  59.         public long nextLong() {
  60.             return Long.parseLong(next());
  61.         }
  62.         public double nextDouble() {
  63.             return Double.parseDouble(next());
  64.         }
  65.     }
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement